C# Нахождение N-го простого числа

Question

Возможный дубликат:
Формула простого числа

Я пытаюсь написать какой-нибудь код на C#, который даст мне n-е простое число, но как только мой код превзойдет 121 как простое число, он начнет возвращать мне неправильные числа.

Теперь это может быть из-за того, что я основал свой код на неправильном алгоритме, но я хотел спросить здесь и посмотреть, если я что-то сделал неправильно.

код запрашивает n-ное простое число 10001 - вывод: 43751 (что, я знаю, неверно)

В любом месте здесь мой код.

int[] p;
int x = 0;
p = new int[10002];
for (int i = 0; i < 1000000; i++)
if (i % 2 != 0)
{
    if (i % 3 != 0)
    {
        if (i % 5 != 0)
        {
            if (i % 7 != 0)
            {
                p[x] = i;
                x++;
                if (x == 10001)
                {
                    Console.WriteLine("{0}", i);
                    break;
                }
            }
        }
    }
}

Answer 1

Это не то, как работает Сито Эратосфена, вы должны прочитать этот раздел из статьи Википедии:

• Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n).
• Первоначально, пусть p равно 2, первое простое число.
• Начиная с p, посчитайте с шагом p и отметьте каждое из этих чисел больше, чем само p в списке. Эти цифры будут 2p, 3p, 4p и т. Д.; обратите внимание, что некоторые из них, возможно, уже были отмечены.
• Найдите первое число больше p в списке, который не отмечен; пусть p теперь равно этому числу (которое является следующим простым).
• Если в списке больше нет номеров без опознавательных знаков, остановитесь. В противном случае повторите с шага 3.

Так что в основном то, что вы думаете, это предел (121из ваших комментариев) это просто пример, который они использовали в этой анимации .gif,

Вот реализация этого метода на C#:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace sieve
{
    class Program
    {
        static void Main(string[] args)
        {
            int maxprime = int.Parse(args[0]);
            ArrayList primelist = sieve(maxprime);

            foreach (int prime in primelist)
                Console.WriteLine(prime);

            Console.WriteLine("Count = " + primelist.Count);
            Console.ReadLine();
        }

        static ArrayList sieve(int arg_max_prime)
        {
            BitArray al = new BitArray(arg_max_prime, true);

            int lastprime = 1;
            int lastprimeSquare = 1;

            while (lastprimeSquare <= arg_max_prime)
            {
                lastprime++;

                while (!(bool)al[lastprime])
                    lastprime++;

                lastprimeSquare = lastprime * lastprime;

                for (int i = lastprimeSquare; i < arg_max_prime; i += lastprime)
                    if (i > 0)
                        al[i] = false;
            }

            ArrayList sieve_2_return = new ArrayList();

            for (int i = 2; i < arg_max_prime; i++)
                if (al[i])
                    sieve_2_return.Add(i);

            return sieve_2_return;
        }
    }
}

Кредиты идут в Rosetta Code

Answer 2

Это потому, что ваш алгоритм невероятно нарушен - вы просто проверяете числа, которые не делятся на 2, 3, 5 и 7, когда вам нужно проверить все * простые числа, меньшие текущего числа.

Быстро прочитайте Fun с простыми числами, в котором есть некоторые из наиболее интуитивно понятных методов поиска простых чисел, хотя алгоритмы поиска простых чисел не входят в тему переполнения стека.

(*) На самом деле вы можете тестировать с меньшим числом простых чисел, чем это, но я хочу сказать, что тестирование с конечным числом простых чисел не будет работать

Обновление: Ваш алгоритм - это не сито Эратосфена, он просто проверяет те же числа, что и сито в случае, если n = 120, Вы должны еще раз прочитать раздел "Описание алгоритма" этой статьи Википедии.

Answer 3

Вам нужно разделить это число со всеми числами до квадратного корня из него.

Например, вам нужно разделить 100 с sqrt(100) = 10, и если он не делится с ним, то это простое число, поэтому все, что вам нужно сделать, это просто

for(int i = 2; i <= Math.Sqrt(number); i++)
{
    if(number%i == 0) return false;
}
return true;

Answer 4

Приведенный ниже код печатает все простые числа до 1000000

        private static void FindPrimeNumber()
        {
            int topNumber = 1000000;
            var numbers = new BitArray(topNumber, true);

            for(int i = 2; i < topNumber; i++)
                if(numbers[i])
                {
                    for(int j = i * 2; j < topNumber; j += i)
                        numbers[j] = false;
                }

            int primes = 0;

            for(int i = 1; i < topNumber; i++)
                if(numbers[i])
                {
                    primes++;
                    Console.Out.WriteLine(i);
                }

            Console.WriteLine();
            Console.Out.WriteLine(primes + " out of " + topNumber + " prime numbers found.");
            Console.ReadLine();
        }