Наиболее эффективный код для первых 10000 простых чисел?

голоса
49

Я хочу напечатать первые 10000 простых чисел. Может кто-нибудь дать мне самый эффективный код для этого? Разъяснения:

  1. Это не имеет значения, если ваш код неэффективен при п> 10000.
  2. Размер кода не имеет значения.
  3. Вы не можете просто жестко закодировать значения каким-либо образом.
Задан 03/08/2008 в 06:45
источник пользователем
На других языках...                            


28 ответов

голоса
41

Решето Аткин , вероятно , что вы ищете, его верхняя граница времени работы составляет O (N / журнал журнал N).

Если вы только запустить номера 1 и более 1 меньше , чем кратные 6, это может быть даже быстрее, так как все простые числа выше 3 1 от некоторого кратного шести. Ресурс для моего заявления

Ответил 03/08/2008 в 07:03
источник пользователем

голоса
35

Я рекомендую сито, либо Решето Эратосфена или решето Аткин.

Сито или Эратосфен, вероятно, является наиболее интуитивным методом нахождения списка простых чисел. В основном вы:

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

Очевидно, что существует довольно много оптимизаций, которые можно сделать, чтобы сделать этот алгоритм работать быстрее, но это основная идея.

Сито Аткин использует подобный подход, но, к сожалению, я не знаю достаточно об этом, чтобы объяснить это вам не знать. Но я знаю, что алгоритм я связывал занимает 8 секунд, чтобы выяснить, все простые числа до 1000000000 на древнем Pentium II-350

Решето Эратосфена Исходный код: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Решето Аткин Исходный код: http://cr.yp.to/primegen.html

Ответил 06/08/2008 в 00:49
источник пользователем

голоса
17

Это не строго против ограничения жестко прописывать, но приходит очень близко. Почему бы не скачать этот программно список и распечатать его, а?

http://primes.utm.edu/lists/small/10000.txt

Ответил 31/08/2008 в 23:20
источник пользователем

голоса
11

GateKiller , как насчет добавления breakк тому , что ifв foreachцикле? Это ускорит вещи много , потому что если , как 6 делятся на 2 вам не нужно проверить с 3 и 5. (я бы голосовать ваше решение в любом случае , если у меня был достаточно репутации :-) ...)

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}
Ответил 27/08/2008 в 21:26
источник пользователем

голоса
9

В Haskell, мы можем записать почти дословно математическое определение решета Эратосфена, « простые натуральные числа выше 1 без каких - либо составных чисел, где композиты найденных перечисления кратного каждого Прайма »:

primes = 2 : minus [3..] (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) 
                                [] primes)

primes !! 10000 это почти мгновенно.

Рекомендации:


Приведенный выше код легко переделан в работе над только шансами, primes = 2:3:minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Сложность времени значительно улучшилась (только о логе - фактор выше оптимального) путем складывания в виде древовидной структуры, и пространство сложность резко улучшена путем производства многоступенчатого простых чисел , в

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p-> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]

(В Haskell круглые скобки используются для группировки, вызов функции обозначена только путем сопоставления, (:)является минусы оператора для списков, и (.)является функциональным оператором состав: (f . g) x = (\y-> f (g y)) x = f (g x)).

Ответил 24/04/2012 в 17:30
источник пользователем

голоса
9

@ Matt: журнал (лог (10000)) составляет ~ 2

Из википедии статьи (которые вы цитируемой) Решето Аткин :

Это сито вычисляет простые числа до N с использованием O(N/log log N)операций только с N 1/2 + O (1) битой памяти. Это немного лучше , чем решето Эратосфена , которая использует O(N) операции и O (N 1/2 (журнал журнал N) / N журнал) бит памяти (AOL Аткин, DJ Bernstein, 2004) . Эти асимптотические вычислительные сложности включают простые оптимизации, такие как колесо факторизации и разделив вычисления на более мелкие блоки.

Учитывая асимптотические вычислительные сложности вдоль O(N)(для Эратосфена) и O(N/log(log(N)))(для Аткиной) , мы не можем сказать (для малых N=10_000) , которые алгоритм , если реализован будет быстрее.

Ахим Flammenkamp писал в решете Эратосфена :

цитируется по:

@ num1

Для интервалов больших около 10 ^ 9, конечно, для тех, кто> 10 ^ 10, решето Эратосфена проигрывает Решето Аткинс и Бернштейна, который использует неприводимые бинарных квадратичных форм. Смотрите их бумаги для фона информаций, а также пункт 5 Ph.D. В. Голуэя Тезис.

Поэтому для 10_000Решето Эратосфена может быть быстрее , чем Решето Аткин.

Для того, чтобы ответить на ОП код prime_sieve.c (цитируется num1)

Ответил 06/10/2008 в 21:03
источник пользователем

голоса
7

Используя GMP, можно было бы написать следующее:

#include <stdio.h>
#include <gmp.h>

int main() {
  mpz_t prime;
  mpz_init(prime);
  mpz_set_ui(prime, 1);
  int i;
  char* num = malloc(4000);
  for(i=0; i<10000; i++) {
    mpz_nextprime(prime, prime);
    printf("%s, ", mpz_get_str(NULL,10,prime));
  }
}

На моем 2,33 ГГц Macbook Pro, он выполняет следующее:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Расчет 1,000,000 простых чисел на том же ноутбуке:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP высоко оптимизирован для такого рода вещи. Если вы действительно хотите понять алгоритмы, написав свой собственный, вы бы посоветовали использовать libGMP под C.

Ответил 29/08/2008 в 08:06
источник пользователем

голоса
4

Я адаптированный код найденный на CodeProject создать следующее:

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

Тестирование это на моем сервере ASP.NET взял rountine около 1 минуты, чтобы бежать.

Ответил 05/08/2008 в 20:55
источник пользователем

голоса
4

Не эффективен на всех, но вы можете использовать регулярные выражения для проверки простых чисел.

/^1?$|^(11+?)\1+$/

Эти тесты , если для строки , состоящей из к « 1» с, к является не простое число (т.е. состоит ли строка из одного « 1» или любое количество « 1» S , которое может быть выражено в виде п -ичный продукта).

Ответил 03/08/2008 в 19:52
источник пользователем

голоса
3

Вот Решето Эратосфена, что я написал в PowerShell несколько дней назад. Она имеет параметр для определения количества простых чисел, которые должны быть возвращены.

#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    param ($target,$count = 0)
    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
    $sieve = @($false) * $sieveBound
    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
    for ($i = 1; $i -le $crossLimit; $i ++) {
        if ($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Found: $prime"
            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                $sieve[$x] = $true
            }
        }
    }
    $primes = @(2)
    for ($i = 1; $i -le $sieveBound; $i ++) {
        if($count -gt 0 -and $primes.length -ge $count) {
            break;
        }
        if($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Output: $prime"
            $primes += $prime
        }
    }
    return $primes
}
Ответил 07/09/2009 в 19:52
источник пользователем

голоса
3

Решето Эратосфена является путь, из - за его простоты и скорости. Моя реализация в C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void)
{
    unsigned int lim, i, j;

    printf("Find primes upto: ");
    scanf("%d", &lim);
    lim += 1;
    bool *primes = calloc(lim, sizeof(bool));

    unsigned int sqrtlim = sqrt(lim);
    for (i = 2; i <= sqrtlim; i++)
        if (!primes[i])
            for (j = i * i; j < lim; j += i)
                primes[j] = true;

    printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
    for (i = 2; i < lim; i++)
        if (!primes[i])
            printf("%d\n", i);

    return 0;
}

CPU Время, чтобы найти простые числа (на Pentium Dual Core E2140 1,6 ГГц, используя одно ядро)

~ 4s для Нт = 100000000

Ответил 21/08/2008 в 00:45
источник пользователем

голоса
2

Deque алгоритм решета упомянутого BenGoldberg заслуживает более подробного рассмотрения, не только потому , что это очень элегантно , но и потому , что иногда может быть полезны на практике ( в отличии от Решета Аткина, который является чисто академическим упражнением).

Основная идея алгоритма DEQUE ситом является использование небольшой, скользящую сито, которое только достаточно большой, чтобы содержать, по меньшей мере, один отдельный мультипликатор для каждого из ныне «активных» главных факторов - то есть те простые числа, квадрат которых не превышает наименьшее число в настоящее время представлены подвижное сито. Еще одно отличие в СОС является то, что DEQUE сито хранит фактические факторы в пазах композитов, а не булевы.

Алгоритм расширяет размер окна сита по мере необходимости, в результате чего достаточно даже производительности в широком диапазоне, пока сито не начинает превышать емкость кэш-памяти L1 ЦП заметно. Последний премьер, который подходит полностью является 25237523 (1,579,791st прайм), что дает грубую приблизительную цифру для разумного рабочего диапазона алгоритма.

Алгоритм является достаточно простым и надежным, и она имеет даже производительность в гораздо более широком диапазоне, чем в несегментированном решете Эратосфена. Последнее намного быстрее, пока его сито полностью вписывается в кэш, то есть до 2 ^ 16 для шансов во-только сито с размером байт-BOOLS. Затем его производительность падает все больше и больше, хотя она всегда остается значительно быстрее, чем дека, несмотря на фору (по крайней мере, в транслируемых языках, как C / C ++, Pascal или Java / C #).

Вот рендеринг DEQUE алгоритма решета в C #, потому что я считаю , что язык - несмотря на многие недостатки - гораздо более практичным для алгоритмов прототипирования и экспериментов , чем в высшей степени громоздкой и педантичного C ++. (Sidenote: Я использую бесплатную LINQPad , который позволяет нырять прямо, без всяких беспорядочности с созданием проектов, мейкфайлов, каталогов или этажерки, и это дает мне ту же степень интерактивности как питон строка).

C # не имеет явного типа , но дека равнину List<int>работает достаточно хорошо для демонстрации алгоритма.

Примечание: эта версия не использует Deque для простых чисел, потому что он просто не имеет смысла палить SQRT (п) из п простых чисел. Что хорошо было бы, чтобы удалить 100 простых чисел и оставить 9900? По крайней мере, таким образом, все простые числа собраны в аккуратный вектор, готовые для дальнейшей обработки.

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

Вот две вспомогательные функции:

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

Возможно , самый простой способ понять алгоритм , это представить его в качестве специального сегментированного решета Эратосфена с размером сегмента 1, сопровождаемой областью переполнения , где штрихи приходят отдыхать , когда они стреляют на конце сегмента. Кроме того , что одна клетка сегмента (он же sieve[0]) уже просеивают , когда мы к нему, потому что он попал под в то время как она была частью области переполнения.

Число , которое представлено sieve[0]проводятся в sieve_base, хотя sieve_frontи window_baseбудет также хорошие имена , которые позволяют провести параллели с кодом Бена или реализацию сегментированных / оконном сит.

Если sieve[0]содержит ненулевое значение , то это значение является фактором sieve_base, который , таким образом , может быть признан в качестве композита. Так как ячейка 0 является кратным этого фактора легко вычислить его следующий шаг, который просто 0 плюс этого фактор. Если эта ячейка будет занята уже другим фактором , то мы просто добавляем фактор снова, и так далее , пока мы не найдем мультипликатор фактора , где ни один другой фактор не в настоящее время припаркованном (расширение сита в случае необходимости). Это также означает , что нет никакой необходимости для хранения текущих рабочих коррекций различных простых чисел от одного сегмента к другому, как в обычном сегментированноге сита. Всякий раз , когда мы находим фактор sieve[0], его текущее рабочее смещение 0.

Нынешний премьер вступает в игру следующим образом. Наглядный может стать только ток после его собственного появления в потоке (т.е. когда он был обнаружен в расцвете сил, потому что не отмечен фактором), и он не останется током до точного момента, когда sieve[0]достигает квадрат. Все нижние кратна этот штрих должны быть вычеркнуто из - за деятельности небольших простых чисел, так же , как в обычном СОСЕ. Но ни один из небольших простых чисел не может вычеркнуть квадрат, так как единственный фактор площади является основным и сам он еще не находится в обращении в данный момент. Это объясняет действия , предпринятые с помощью алгоритма в случае sieve_base == current_prime_squared(что означает sieve[0] == 0, кстати).

Теперь дело sieve[0] == 0 && sieve_base < current_prime_squaredлегко объяснимо: это означает , что sieve_baseне может быть кратны любым из простых чисел , меньших , чем нынешний премьер, иначе он был бы отмечен как композит. Я не могу быть выше кратен текущим штрих либо, так как его значение меньше площади текущего Прайма. Следовательно , оно должно быть новым премьером.

Алгоритм, очевидно, навеян решета Эратосфена, но в равной степени очевидно, что это очень разные. Решето Эратосфена получает свою высокую скорость из-за простоты его элементарных операций: один единый индекс сложение и один магазин для каждого шага операций все, что она делает в течение длительного времени.

Вот простое, сегментированное Решето Эратосфена , что я обычно использую для просеивания фактора простых чисел в диапазоне UShort, то есть до 2 ^ 16. Для этого поста я изменил его на работу за 2 ^ 16, подставляя intдляushort

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

Когда просеивания первого 10000 простых числа типичного кэш L1 из 32 KiByte будут превышены, но функция по-прежнему очень быстро (доли миллисекунды даже в C #).

Если сравнить этот код DEQUE решето, то легко видеть, что операции DEQUE сите намного более сложным, и он не может эффективно амортизировать свои накладные расходы, так как он всегда делает кратчайший отрезок переезды-офф подряд (ровно один одиночный переход-офф, после пропуска всех мультипликаторов, которые были вычеркнуты уже).

Примечание: C # код используют intвместо uintпотому что новые компиляторы имеют привычку генерировать некачественный код uint, вероятно, для того , чтобы подтолкнуть человек к подписанным целыхам ... В версии C ++ кода выше , я использовал в unsignedтечение, естественно; ориентир должен быть в C ++ , потому что я хотел его быть основан на якобы адекватный типе DEQUE ( std::deque<unsigned>, не было никакого прироста производительности от использования unsigned short). Вот цифры для моего Haswell ноутбука (VC ++ 2015 / x64):

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

Примечание: C # времена почти точно в два раза C ++ тайминги, что довольно хорошо для C # и показывает , что List<int>не сутулиться , даже если злоупотреблять , как дека.

Простой код сито еще дует Deque из воды, даже если он уже работает за пределами своего нормального рабочего диапазона (размер кэша L1 превышен на 50%, с сопутствующим обмолота кэш). Доминирующая часть здесь является чтение из просеянных простых чисел, и это не влияет много проблемы кэша. В любом случае функция была разработана для просеивания факторов факторов, то есть на уровне 0 в иерархии сита 3 уровня, и, как правило, он должен возвращать только несколько сот факторов или небольшое число тысяч. Следовательно, его простота.

Производительность может быть улучшена за счет более чем на порядок величины, используя сегментированное сито и оптимизации кода для извлечения просеянной простых чисел (ступенчато мод 3 и раскатывают в два раза, или по модулю 15 и раскатывают один раз), и еще более производительность может быть вытеснены из код с помощью мод 16 или 30 мод колеса со всей отделкой (т.е. полная развертка для всех остатков). Нечто подобное описано в моем ответе Найти простое Позиционируется простое число над по обзору кода, где обсуждалась аналогичная проблема. Но это трудно понять точку в улучшении раз к югу миллисекунды для разовой задачи ...

Чтобы положить вещи немного в перспективу, вот C ++ таймингов для просеивания до 100.000.000:

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

В противоположность этому, сегментированный сито в C # с несколькими прибамбасами делает ту же работу в 95 мс (не C ++ тайминги доступной, так как я код вызовы только в C # на данный момент).

Вещи могут выглядеть решительно отличаться в интерпретируемый язык, как Python, где каждая операция имеет значительные издержки и накладные расходы переводчика затмевает все различия, связанные с прогнозируемым против ошибочных ветвей или суб-цикла OPS (сдвиг, сложение) против опс нескольких циклов (размножения , и, возможно, даже деление). Это неизбежно подорвет простота преимущество решета Эратосфена, и это может сделать Deque решение немного более привлекательным.

Кроме того , многие из таймингов сообщенных других респондентов в этой теме, вероятно , доминирует время вывода . Это совершенно другая война, где мое главное оружие является простым классом , как это:

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

Это занимает менее 1 мс для записи 10000 (отсортированные) номера. Это статический класс, так как он предназначен для текстового включения в кодовом вызов представления, с минимумом суеты и без накладных расходов.

В общем , я нашел , что это будет намного быстрее , если сфокусированы работа выполняется на целых партий, то есть сито определенный диапазон, а затем извлечь все простые числа в вектор / массив, а затем взрыв из всего массива, затем просеивают следующий круг и так далее, вместо того , смешиваясь все вместе. Наличие отдельных функций сфокусированных на конкретных задачах и делает его легче смешивать и сочетать, это позволяет повторно использовать, и это облегчает развитие / тестирование.

Ответил 19/04/2016 в 17:07
источник пользователем

голоса
2

В Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Ответил 22/02/2010 в 08:45
источник пользователем

голоса
2

Сито , кажется, неправильный ответ. Сито дает простые числа до числа N , а не в первые N простых чисел. Run @Imran или Szeto @ Андрей, и вы получите простые числа до N.

Сито еще может быть полезной, если вы продолжаете пытаться решета для более больших чисел, пока не достиг определенного размера результирующего набора, а также использовать некоторые кэширование чисел уже полученных, но я не считаю, что это все равно будет не быстрее, чем решение, как @ Пат ,

Ответил 19/06/2009 в 19:12
источник пользователем

голоса
2

Адаптация и вслед за GateKiller , вот окончательный вариант , который я использовал.

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

Это в основном то же самое, но я добавил «перерыв на Sqrt» предложения и изменил некоторые переменные вокруг, чтобы сделать его пригодным для меня лучше. (Я работал над Эйлера и нуждался в 10001th прайм)

Ответил 16/02/2009 в 06:17
источник пользователем

голоса
1

Использование Решето Эратосфена, вычисление достаточно быстро по сравнению с «известной шириной» алгоритм простых чисел.

С помощью псевдокода от его вики ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), я в состоянии иметь решение на C #.

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes (100000000) принимает 2s и 330ms.

Примечание : Значение может изменяться в зависимости от характеристик аппаратных средств .

Ответил 12/05/2016 в 03:40
источник пользователем

голоса
1

Вот решение С ++, используя форму SoE:

#include <iostream>
#include <deque>

typedef std::deque<int> mydeque;

void my_insert( mydeque & factors, int factor ) {
    int where = factor, count = factors.size();
    while( where < count && factors[where] ) where += factor;
    if( where >= count ) factors.resize( where + 1 );
    factors[ where ] = factor;
}

int main() {
    mydeque primes;
    mydeque factors;
    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
    int cnt = 2;
    factors.resize(3);
    std::cout << "2 3 ";

    while( cnt < 10000 ) {
        int factor = factors.front();
        maybe_prime += 2;
        if( factor ) {
            my_insert( factors, factor );
        } else if( maybe_prime < a_square_prime ) {
            std::cout << maybe_prime << " ";
            primes.push_back( maybe_prime );
            ++cnt;
        } else {
            my_insert( factors, a_prime );
            a_prime = primes.front();
            primes.pop_front();
            a_square_prime = a_prime * a_prime;
        }
        factors.pop_front();
    }

    std::cout << std::endl;
    return 0;
}

Обратите внимание, что эта версия Сита может вычислить простые числа бесконечно.

Также обратите внимание, что STL dequeзанимает O(1)время , чтобы выполнить push_back, pop_frontи произвольный доступ , хотя индексация.

resizeОперация занимает O(n)время, где nэто число элементов добавляется. Из - за того , как мы используем эту функцию, мы можем рассматривать это малая константа.

Тело whileв цикле обработки my_insertвыполняется O(log log n)раз, где nравно переменные maybe_prime. Это происходит потому , что условие Экспрессия whileбудет вычисляться правда один раз для каждого простого фактора maybe_prime. Смотрите « делитель функция » на Википедии.

Умножив количество раз , что my_insertназывается, показывает , что он должен занять O(n log log n)время , чтобы перечислить nпростые числа ... что неудивительно, временная сложность которого Решето Эратосфена должно иметь.

Однако, в то время как этот код является эффективным, это не самым эффективным ... Я бы настоятельно рекомендую использовать специализированную библиотеку для генерации простых чисел, таких как primesieve . Любой действительно эффективный, хорошо оптимизированное решение, потребуется больше кода , чем кто - либо хочет ввести в Stackoverflow.

Ответил 16/04/2016 в 18:33
источник пользователем

голоса
1

Следующий код Mathcad рассчитали первый миллион простых чисел в возрасте до 3 минут.

Имейте в виду, что это будет использовать с плавающей точкой в ​​два раза для всех чисел и в основном интерпретируется. Я надеюсь, что синтаксис ясно.

введите описание изображения здесь

Ответил 02/03/2014 в 02:15
источник пользователем

голоса
1

Вот мой VB 2008 код, который находит все простые числа <10000000 в течение 1 мин 27 СЕК на моем рабочем ноутбуке. Он пропускает даже номера и ищет только простые числа, которые являются <SQRT тестового числа. Он предназначен только для поиска простых чисел от 0 до Sentinal значения.

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
Ответил 11/03/2011 в 03:25
источник пользователем

голоса
0

Так как вы хотите, первые 10000 простых чисел только, а не сложный алгоритм кодирования, я предлагаю следующее

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

Теперь вызов является простым, как вам это нужно

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Ответил 16/11/2018 в 05:34
источник пользователем

голоса
0

Я могу дать вам несколько советов, вы должны реализовать.

  1. Для каждого номера, получить половину от этого числа. Например, для проверки 21, только получить остаток от деления его из диапазона 2-10.
  2. Если его нечетное число, только разделить на нечетное число, и наоборот. Такие, как на 21, разделить с 3, 5, 7, только 9.

Наиболее эффективный метод, который я получил до сих пор.

Ответил 29/07/2018 в 19:25
источник пользователем

голоса
0

Используя метод Array.prototype.find () в JavaScript. 2214.486 мс

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start++ < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count++
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i++
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms
Ответил 09/06/2018 в 21:49
источник пользователем

голоса
0

Вот код, который я сделал:


enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   

unsigned long int n;

int prime(unsigned long int);

scanf("%ld",&n);

unsigned long int val;

for(unsigned long int i=0;i<n;i++)
{
    int flag=0;

    scanf("%ld",&val);

    flag=prime(val);

    if(flag==1)
        printf("yes\n");

    else
        printf("no\n");
}

return 0;

}

int prime(unsigned long int n)
{

if(n==2) return 1;

else if (n == 1||n%2==0)  return 0;

for (unsigned long int i=3; i<=sqrt(n); i+=2)
    if (n%i == 0)
        return 0;

return 1;
}
Ответил 20/01/2018 в 15:50
источник пользователем

голоса
0

Вот мой код , который находит первые 10000 простых чисел в 0.049655 сек на моем ноутбуке, первые 1,000,000 простые числа в возрасте до 6 секунд и первый 2000000 в течение 15 секунд
небольшое объяснение. Этот метод использует 2 методы , чтобы найти простое число

  1. прежде всего любое не простого число представляет собой совокупность кратных простых чисел так, этот тест-код пути деления номера теста на меньшие простых числах вместо любого числа, при этом уменьшается расчет по крайней мере в 10 раз в течение 4-значного числа, и даже больше для больший номер
  2. во-вторых, кроме деления на расцвете сил, он делит только простые числа, которые меньше или равна корню из числа ПРОХОДЯТ ПРОВЕРКУ дальнейшего сокращения вычислений значительно, это работает, потому что любое число, которое больше, чем корень из числа, будет иметь номер партнера в том, что должно быть меньше, чем корень из числа, но так как мы проверили все числа меньшие, чем уже корень, поэтому нам не нужно возиться с номером, большим, чем корень из числа испытывается.

Пример вывод для первых 10000 простых чисел
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Вот код на языке C, введите 1 , а затем 10000 распечатать первые 10000 простых чисел.
Изменить: Я забыл это содержит математическую библиотеку, если вы на окнах или визуальной студии , чем должно быть хорошо , но на Linux вы должны скомпилировать код , используя -lm аргумент или код не может работать
Пример: GCC -Wall -o «% е " "% F" -lm

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}
Ответил 06/05/2017 в 11:48
источник пользователем

голоса
0

Я работаю над найти простые числа в течение года. Это то, что я нашел, чтобы быть самым быстрым:

import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
    public static void main(String[] args) {
        primelist primes = new primelist();
        primes.insert(3);
        primes.insert(5);
        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
        file.getParentFile().mkdirs();
        long time = System.nanoTime();
        try{
            PrintWriter printWriter = new PrintWriter ("file0024.txt"); 
            int linenum = 0;
            printWriter.print("2");
            printWriter.print (" , ");
            printWriter.print("3");
            printWriter.print (" , ");
            int up;
            int down;           
            for(int i =1; i<357913941;i++){//
                if(linenum%10000==0){
                    printWriter.println ("");
                    linenum++;
                }
                down = i*6-1;
                if(primes.check(down)){
                    primes.insert(down);
                    //System.out.println(i*6-1);
                    printWriter.print ( down );
                    printWriter.print (" , ");
                    linenum++;  
                }
                up = i*6+1;
                if(primes.check(up)){
                    primes.insert(up);
                    //System.out.println(i*6+1);
                    printWriter.print ( up );
                    printWriter.print (" , ");
                    linenum++;  
                }
            }
            printWriter.println ("Time to execute");
            printWriter.println (System.nanoTime()-time);
            //System.out.println(primes.length);
            printWriter.close ();
        }catch(Exception e){}
    } 
}
class node{
    node next;
    int x;
    public node (){
        node next;
        x = 3;
    }
    public node(int z) {
        node next;
        x = z;
    }
}
class primelist{
    node first;
    int length =0;
    node current;
    public void insert(int x){
        node y = new node(x);
        if(current == null){
            current = y;
            first = y;
        }else{
            current.next = y;
            current = y;
        }
        length++;
    }
    public boolean check(int x){
        int p = (int)sqrt(x);
        node y = first;
        for(int i = 0;i<length;i++){
            if(y.x>p){
                return true;
            }else if(x%y.x ==0){
                return false;
            }
            y = y.next;
        }
        return true;
    }
}

1902465190909 нано секунд, чтобы добраться до 2147483629, начиная с 2.

Ответил 14/08/2016 в 00:20
источник пользователем

голоса
0

Я потратить некоторое время на написание программы вычисления много простых числа , и это код , я использовал для расчета текстового файла , содержащего первые 1.000.000.000 простых чисел. Это на немецком языке , но интересная часть является методом calcPrimes(). Штрихи, хранятся в массиве с именем Primzahlen. Я рекомендую 64 - битный процессор , так как расчеты с 64 - битными целыми числами.

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}
Ответил 23/04/2012 в 20:46
источник пользователем

голоса
0

Я написал это с помощью Python, как я только начал изучать его, и он работает прекрасно. Десятитысячной премьер генерирует этот код так же , как указано в http://primes.utm.edu/lists/small/10000.txt . Чтобы проверить, nявляется простым или нет, деления nчисел от 2до sqrt(n). Если какой - либо из этого диапазона числа отлично разделяет , nто это не простое.

import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
    b = math.sqrt(c)
    b = int(b)
    x = 0
    for b in range(2,b+1):
        e  = c % b
        e = int(e)
        if (e == 0):
            x = x+1
    if (x == 0):
        print("%d is prime number" % c)
        count = count + 1
print("Total number of prime till %d is %d" % (a,count))
Ответил 27/12/2010 в 18:37
источник пользователем

голоса
-1
using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}
Ответил 08/05/2012 в 05:15
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more