Я хочу напечатать первые 10000 простых чисел. Может ли кто-нибудь дать мне самый эффективный код для этого? Разъяснения:
Сито Аткина, вероятно, то, что вы ищете, его верхнее время пробега - O (N/log log N).
Если вы выполняете только числа на 1 и 1 меньше, чем кратные 6, это может быть еще быстрее, так как все простые числа выше 3 равны 1 от нескольких кратных шести. Ресурс для моего утверждения
Я рекомендую сито, Сито Эратосфена или Сито Аткина.
Сито или Эратосфен, вероятно, самый интуитивный метод нахождения списка простых чисел. В основном вы:
Очевидно, существует довольно много оптимизаций, которые могут быть сделаны для ускорения работы этого алгоритма, но это основная идея.
Решетка Аткина использует подобный подход, но, к сожалению, я недостаточно знаю об этом, чтобы объяснить это вам. Но я знаю, что связанный мной алгоритм занимает 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
Это не строго против ограничения жесткой кодировки, но идет ужасно близко. Почему бы не программно загрузить этот список и не распечатать его?
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 + " ");
}
}
В Хаскеле мы можем почти дословно записать математическое определение сита Эратосфена: "простые числа - это натуральные числа выше 1 без каких-либо составных чисел, где композиты находятся путем перечисления каждого простого множителя":
import Data.List.Ordered (minus, union)
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 [email protected](x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(В Haskell круглые скобки используются для группировки, вызов функции обозначается просто сопоставлением, (:) является оператором cons для списков, а (.) является оператор функциональной композиции: (f . g) x = (\y -> f (g y)) x = f (g x)).
@Matt: log (log (10000)) ~ 2
Из статьи wikipedia (которую вы указали) Сито Аткина:
Это сито вычисляет простые числа до N используя операции
O(N/log log N)с только N 1/2 + o (1) бит памяти. То есть немного лучше, чем сито Эратосфен, который используетO(N)операций и O (N 1/2 (log log N)/log N) бит памяти (A.O.L.Atkin, D.J. Bernstein, 2004). Эти асимптотические вычислительные сложности включают простые оптимизации, такие как колесо факторизации и расщепления вычисление для меньших блоков.
Учитывая асимптотические вычислительные сложности вдоль O(N) (для Эратосфена) и O(N/log(log(N))) (для Аткина), мы не можем сказать (при малом N=10_000), какой алгоритм будет реализован быстрее.
Ахим Фламменкамп написал в Сито Эратосфена:
процитировано:
@num1
Для интервалов, больших около 10 ^ 9, для тех > 10 ^ 10, сито Эратосфен превосходит Сито Аткинса и Бернштейна, которое использует неприводимую двоичную квадратичную формы. См. Их статью для фона информацию, а также пункт 5 W. Galway Ph.D. Тезис.
Поэтому для 10_000 Сито эратосфенов может быть быстрее, чем сито Аткина.
Чтобы ответить OP, код prime_sieve.c (процитировано num1)
Используя 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));
}
}
На моем MacBook Pro 2,33 ГГц он выполняется следующим образом:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
Вычисление 1000 000 простых чисел на одном ноутбуке:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP очень оптимизирован для такого рода вещей. Если вы действительно не хотите понимать алгоритмы, написав свои собственные, вам следует использовать libGMP под C.
Неэффективен вообще, но вы можете использовать регулярное выражение для проверки простых чисел.
/^1?$|^(11+?)\1+$/
Это проверяет, если для строки, состоящей из k "1" s, k не является простым (т.е. состоит ли строка из одного "1" или любого числа "1" s, которое может быть выраженное как n-арный продукт).
Я скорректировал код, найденный на 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 заняло около 1 минуты для запуска.
Сито Эратосфена - это путь, из-за которого простота и скорость. Моя реализация в 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 для lim = 100 000 000
Вот сито Эратосфена, которое я написал в 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
}
Адаптация и последующее от 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;
}
Это в основном то же самое, но я добавил предложение "break on Sqrt" и изменил некоторые переменные вокруг, чтобы сделать его пригодным для меня лучше. (Я работал над Эйлером и нуждался в 10001-м премьер-классе)
Сито кажется неправильным ответом. Сито дает вам простые до число N, а не простые первые N. Запустите @Imran или @Andrew Szeto, и вы получите простые числа до N.
Сито может по-прежнему использоваться, если вы продолжаете пробовать сита для получения большего количества чисел, пока не нажмете определенный размер вашего набора результатов, и используйте некоторое кэширование уже полученных чисел, но я считаю, что это все равно будет не быстрее, чем решение как @Pat's.
В Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
алгоритм deque сита, упомянутый BenGoldberg, заслуживает более пристального внимания не только потому, что он очень изящный, но также потому, что он может иногда быть полезным на практике (в отличие от сита из Аткина, что является чисто академическим упражнением).
Основная идея алгоритма deque sieve заключается в использовании небольшого скользкого сита, который достаточно велик, чтобы содержать по крайней мере один отдельный кратный для каждого из активных "активных" основных факторов - то есть тех простых чисел, квадрат которых не превышает самое низкое число, которое в настоящее время представлено движущимся ситом. Еще одно отличие от SoE заключается в том, что сито deque хранит фактические факторы в слотах композитов, а не булевых.
Алгоритм расширяет размер окна сита по мере необходимости, что приводит к довольно равномерной производительности в широком диапазоне до тех пор, пока сито не начнет значительно превышать емкость кэша процессора L1. Последний штрих, который подходит полностью, составляет 25 237 523 (1 579 791 шт.), Что дает приблизительную цифру шарового поля для разумного рабочего диапазона алгоритма.
Алгоритм довольно прост и прочен, и он имеет даже производительность в гораздо более широком диапазоне, чем несегментированное сито Eratosthenes. Последнее намного быстрее, так как его сито полностью помещается в кеш, то есть до 2 ^ 16 для сита с шансами только с размерами байтов. Затем его производительность падает все больше и больше, хотя она всегда остается значительно быстрее, чем дека, несмотря на гандикап (по крайней мере, на скомпилированных языках, таких как C/С++, Pascal или Java/С#).
Вот рендеринг алгоритма deque sieve в С#, потому что я нахожу этот язык - несмотря на его многочисленные недостатки - гораздо более практичным для прототипирования алгоритмов и экспериментов, чем чрезвычайно громоздкий и педантичный С++. (Sidenote: Я использую бесплатный LINQPad, который дает возможность погрузиться прямо, без всякой беспомощности с настройкой проектов, make файлы, каталоги или многое другое, и это дает мне такую же степень интерактивности, что и приглашение python).
С# не имеет явного типа deque, но простой List<int> работает достаточно хорошо для демонстрации алгоритма.
Примечание: эта версия не использует deque для простых чисел, потому что просто не имеет смысла выкидывать sqrt (n) из n простых чисел. Какая польза, чтобы удалить 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, сопровождаемое областью переполнения, где простые числа останавливаются, когда они стреляют по концу сегмента. За исключением того, что одна ячейка сегмента (a.k.a. sieve[0]) уже была просеяна, когда мы добираемся до нее, потому что она прошла, пока она была частью области переполнения.
Число, представленное sieve[0], сохраняется в sieve_base, хотя sieve_front или window_base также будут хорошими именами, которые позволят провести параллели с кодом Бена или реализациями сегментированных/оконных сит.
Если sieve[0] содержит ненулевое значение, то это значение является фактором sieve_base, которое, таким образом, может быть распознано как составное. Поскольку ячейка 0 кратно этому коэффициенту, легко вычислить ее следующий прыжок, который просто равен 0 плюс этот коэффициент. Если эта ячейка занята уже другим фактором, мы просто добавляем множитель снова и так далее, пока не найдем кратное множителю, где в настоящее время нет другого фактора (расширяя сито, если необходимо). Это также означает, что нет необходимости хранить текущие рабочие смещения различных простых чисел от одного сегмента к другому, как в обычном сегментированном сите. Всякий раз, когда мы находим коэффициент в sieve[0], его текущее рабочее смещение равно 0.
Текущий предел вступает в игру следующим образом. Простое может стать текущим только после его собственного появления в потоке (т.е. Когда оно было определено как простое, потому что не отмечено с коэффициентом), и оно останется текущим до момента, когда sieve[0] достигнет своего квадрата. Все нижние кратные этого штриха должны были быть удалены из-за активности меньших простых чисел, как в обычном SoE. Но ни один из меньших простых чисел не может ударить по квадрату, так как единственным фактором квадрата является сам премьер, и он пока не находится в обращении. Это объясняет действия, предпринятые алгоритмом в случае 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, но функция все еще очень быстрая (доля миллисекунды даже в С#).
Если вы сравните этот код с ситом deque, то легко увидеть, что операции сита deque намного сложнее, и он не может эффективно амортизировать его накладные расходы, поскольку он всегда делает кратчайший путь пересечения в строке (ровно одно единственное скрещивание после пропущения всех кратных, которые уже были скрещены).
Примечание: код С# использует int вместо uint, потому что новые компиляторы имеют привычку генерировать нестандартный код для uint, возможно, чтобы подтолкнуть людей к целым знакам со знаком... В версии С++ код выше, я использовал unsigned повсюду, естественно; контрольный показатель должен был быть на С++, потому что я хотел, чтобы он основывался на предположительно адекватном типе deque (std::deque<unsigned>, при использовании unsigned short не было увеличения производительности). Вот цифры для моего ноутбука Haswell (VС++ 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
Примечание: времена С# почти точно удваивают тайм-ауты С++, что довольно хорошо для С#, а tt показывает, что List<int> не является сутулой, даже если он злоупотребляет как deque.
Простой ситовый код по-прежнему удаляет deque из воды, даже несмотря на то, что он уже работает за пределами своего обычного рабочего диапазона (размер кеша L1 превышен на 50%, сопутствующий сбой кэша). Главной частью здесь является считывание пропущенных простых чисел, и это не сильно зависит от проблемы с кешем. В любом случае функция была разработана для просеивания факторов факторов, то есть уровня 0 в трехуровневой иерархии сит, и обычно она должна возвращать только несколько сотен факторов или небольшое количество тысяч. Отсюда его простота.
Производительность может быть улучшена более чем на порядок, используя сегментированное сито и оптимизируя код для извлечения просеянных простых чисел (ступенчатый mod 3 и развернутый дважды, или mod 15 и разворачиваемый один раз), и, тем не менее, выдавливается из кода с помощью колесика мод 16 или мод 30 со всеми обрезками (т.е. полным разворачиванием для всех остатков). Что-то вроде этого объясняется в моем ответе на Найти первично позиционированное правое число над обзором кода, где обсуждалась аналогичная проблема. Но трудно понять суть улучшения в течение нескольких миллисекунд раз для одноразовой задачи...
Чтобы взглянуть на вещи в перспективе, вот тайм-ауты С++ для просеивания до 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
Напротив, сегментированное сито в С# с несколькими колокольчиками и свистками выполняет одно и то же задание за 95 мс (нет тайм-аутов С++, так как в настоящее время я вызываю проблемы с кодом только в С#).
В интерпретируемом языке, таком как 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;
}
}
}
Для записи 10000 (отсортированных) чисел требуется менее 1 мс. Это статический класс, потому что он предназначен для текстового включения в представления о запросах кодирования, с минимальными издержками и нулевыми служебными данными.
В общем, я обнаружил, что это намного быстрее, если целенаправленная работа выполняется на целых партиях, что означает сито определенного диапазона, затем извлекает все простые числа в вектор/массив, затем выдает весь массив, затем просеивает следующий диапазон и и так далее, вместо того, чтобы смешивать все вместе. Наличие отдельных функций, сосредоточенных на конкретных задачах, также облегчает смешивание и сопоставление, позволяет повторно использовать и облегчает разработку/тестирование.
Вот мой код VB 2008, который находит все простые числа и 10 000 000 за 1 минуту 27 секунд на моем рабочем ноутбуке. Он пропускает четные числа и ищет только простые числа, sqrt тестового номера. Он предназначен только для того, чтобы находить простые числа от 0 до отважного значения.
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
Следующий код Mathcad рассчитал первые миллионы простых чисел менее чем за 3 минуты.
Имейте в виду, что это будет использование двойных чисел с плавающей запятой для всех чисел и в основном интерпретируется. Я надеюсь, что синтаксис понятен.
Вот С++-решение, используя форму 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 будет оцениваться как true для каждого простого коэффициента maybe_prime. См. " Функция Divisor" в Википедии.
Вызывается умножение на количество раз my_insert, показывает, что он должен принять O(n log log n) время для перечисления n простых чисел... что, что неудивительно, временная сложность, которую должно иметь сито Эратосфена.
Однако, хотя этот код эффективен, он не является наиболее эффективным... Я бы настоятельно предложил использовать специализированную библиотеку для генерации простых чисел, например primesieve. Любое действительно эффективное, хорошо оптимизированное решение займет больше кода, чем кто-либо хочет ввести в Stackoverflow.
Используя Сито Эратосфена, вычисление происходит довольно быстро по сравнению с алгоритмом простых чисел "общеизвестный".
Используя псевдокод из него wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), я смогу получить решение на С#.
/// 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) занимает 2 с и 330 мс.
ПРИМЕЧАНИЕ. Значение может зависеть от технических характеристик оборудования.
Я написал это с помощью python, так как я только начал его изучать, и он отлично работает. 10 000-го числа сгенерируют этот код так же, как указано в 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))
Я провожу некоторое время, записывая программу, вычисляющую много простых чисел, и это код, который я использую для вычисления текстового файла, содержащего первые 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);
}
}
}
Я работаю над поиском простых чисел около года. Это то, что я считаю самым быстрым:
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 nano секунд, чтобы добраться до 2147483629, начиная с 2.
Вот мой код, который находит
первые 10 000 простых чисел в 0.049655 сек на моем ноутбуке, первые 1 000 000 простых чисел менее чем за 6 секунд и первые 2 000 000 за 15 секунд
Немного объяснения. Этот метод использует 2 метода для нахождения простого числа
Пример вывода для первого 10 000 простых чисел
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Вот код на языке C,
Введите 1, а затем 10 000, чтобы распечатать первые 10000 простых чисел.
Редактирование: я забыл, что это содержит математическую библиотеку, если вы находитесь в окнах или визуальной студии, чем это должно быть хорошо, но в Linux вы должны скомпилировать код с использованием аргумента -lm или код может не работать.
Пример: gcc -Wall -o "% e" "% 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);
}
Вот код, который я сделал:
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;
}
Использование метода 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
Я могу дать вам несколько советов, вы должны это реализовать.
Самый эффективный метод, который я получил до сих пор.
Так как вы хотите только первые 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
}
}
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();
}
}
}