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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вы можете сделать это, используя подход динамического программирования снизу вверх, называемый Решетом Эратосфена. В основном вы создаете логический кеш всех чисел до 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;

    }
}

Это то, что я разработал для 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;
}

Сито Аткина также является лучшим алгоритмом для реализации в этом случае, и для него требуется всего O (N) операций и O (N) пространства. Подробное описание алгоритм и псевдокод.