Вернуть все простые числа меньше М

Question

Учитывая целое число M., вернуть все простые числа, меньшие, чем M.

Дайте алгоритм настолько хорош, насколько вы можете.Необходимо учитывать сложность времени и пространства.

Answer 1

Сито Эратосфена - хорошее место для начала.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

Пара дополнительных подсказок по производительности:

1. Вам нужно проверить только до квадратного корня из M, поскольку каждое составное число имеет хотя бы один простой множитель меньше или равен квадратному корню
2. Вы можете кэшировать известные простые числа при их создании и проверять последующие числа только по числам в этом списке (вместо каждого числа ниже sqrt(M))
3. Вы можете явно пропустить четные числа (кроме, конечно, 2)

Answer 3

Обычный ответ заключается в реализации Сита Эратосфена , но это действительно единственное решение для поиска списка всех простых чисел, меньших, чем N. Если вы хотите тесты простоты для конкретных чисел, есть лучшие варианты для больших чисел.

Answer 4

Сито Эратосфена это хорошо.

Answer 5

Сито Аткина также является лучшим алгоритмом для реализации в этом случае, и он требует только O (N) операций и O (N) места. Пожалуйста, обратитесь https://en.wikipedia.org/wiki/Sieve_of_Atkin для подробного объяснения алгоритма и псевдокода.

Answer 6

Это то, что я разработал для Seive of Eratosthenes. Конечно, были бы лучшие реализации.

// находит число простых чисел меньше длины

private static int findNumberOfPrimes(int length) {
    int numberOfPrimes = 1;
    if (length == 2) {
        return 1;
    }

    int[] arr = new int[length];
    //creating an array of numbers less than 'length'
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i + 1;
    }
    //starting with first prime number 2, all the numbers divisible by 2(and upcoming) is replaced with -1
    for (int i = 2; i < arr.length && arr[i] != -1; i++) {

        for (int j = i; j < arr.length; j++) {
            if (arr[j] % arr[i] == 0) {
                arr[j] = -1;
                numberOfPrimes += 1;
            }
        }

    }
    return numberOfPrimes;
}

Answer 7

Вы можете сделать это, используя подход динамического программирования «снизу вверх», который называется Сито Эратосфена. По сути, вы создаете логический кеш всех чисел до n и помечаете каждый кратный каждому числу как not_prime. Дальнейшая оптимизация может быть достигнута путем проверки только до sqrt (n), поскольку любое составное число будет иметь хотя бы один делитель меньше, чем sqrt (n)

    public int countPrimes(int n) {
    if(n==0){
        return 0;
    }else{
        boolean[] isPrime=new boolean[n];
        for(int i=2;i<n;i++){
            isPrime[i]=true;
        }

        /* Using i*i<n instead of i<Math.sqrt(n)
         to avoid the exepnsive sqrt operation */
        for(int i=2;i*i<n;i++){
           if(!isPrime[i]){
               continue;
           }
            for(int j=i*i;j<n;j+=i){
                isPrime[j]=false;
            }
        }

        int counter=0;
        for(int i=2;i<n;i++){
            if(isPrime[i]){
                counter++;
            }
        }

        return counter;

    }
}

Answer 8

π (n) считать простые числа, меньшие или равные n.Пафнуты Чебышев показал, что если существует

lim n → ∞ π (n) / (n / ln (n))

, то оно существуетравно 1. Есть много значений, которые приблизительно равны π (n) на самом деле, как показано в таблице.

Это дает правильное число простого числа для этогоЧисловой формат. Надеюсь, это будет полезно.

Answer 9

Я начинающий программист на c # (и новичок в SO), так что это может быть немного многословно.тем не менее, я проверил это, и я работаю.

вот что я придумал:

for (int i = 2; i <= n; i++)
{
    while (n % i == 0)
    {
        Console.WriteLine(i.ToString());
        n /= i;
    }
}
Console.ReadLine();