Создайте список простых чисел до определенного числа

Я пытаюсь создать список простых чисел ниже 1 миллиарда. Я пытаюсь это сделать, но такая структура довольно дерьмовая. Какие-либо предложения?

a <- 1:1000000000 d <- 0 b <- for (i in a) {for (j in 1:i) {if (i %% j !=0) {d <- c(d,i)}}} 

10 Solutions collect form web for “Создайте список простых чисел до определенного числа”

Это реализация алгоритма решета Эратосфена в R.

 sieve < - function(n) { n <- as.integer(n) if(n > 1e6) stop("n too large") primes < - rep(TRUE, n) primes[1] <- FALSE last.prime <- 2L for(i in last.prime:floor(sqrt(n))) { primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE last.prime <- last.prime + min(which(primes[(last.prime+1):n])) } which(primes) } sieve(1000000) 

Это сито, отправленное Джорджем Дантасом, является хорошей отправной точкой. Вот гораздо более быстрая версия с временем выполнения для 1e6 простых чисел 0,095, а не 30 секунд для исходной версии.

 sieve < - function(n) { n <- as.integer(n) if(n > 1e8) stop("n too large") primes < - rep(TRUE, n) primes[1] <- FALSE last.prime <- 2L fsqr <- floor(sqrt(n)) while (last.prime <= fsqr) { primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE sel <- which(primes[(last.prime+1):(fsqr+1)]) if(any(sel)){ last.prime <- last.prime + min(sel) }else last.prime <- fsqr+1 } which(primes) } 

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

Вот рекурсивная функция, использующая mod, но векторизованная. Он возвращается на 1e5 почти мгновенно и 1e6 менее чем за 2 секунды.

 primes < - function(n){ primesR <- function(p, i = 1){ f <- p %% p[i] == 0 & p != p[i] if (any(f)){ p <- primesR(p[!f], i+1) } p } primesR(2:n) } 

Следующий - не рекурсивный и более быстрый. Нижеприведенный код делает простые цифры до 1e6 примерно на 1,5 секунды на моей машине.

 primest < - function(n){ p <- 2:n i <- 1 while (p[i] <= sqrt(n)) { p <- p[p %% p[i] != 0 | p==p[i]] i <- i+1 } p } 

BTW, пакет spuRs имеет ряд основных функций поиска, включая сито E. Не проверял, что такое скорость для них.

И хотя я пишу очень длинный ответ ... вот как вы проверите R, если одно значение является простым.

 isPrime < - function(x){ div <- 2:ceiling(sqrt(x)) !any(x %% div == 0) } 

Лучший способ, которым я знаю, генерировать все простые числа (без вникания в сумасшедшую математику) – использовать Сито Эратосфена .

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

Этот метод должен быть более быстрым и простым.

 allPrime < - function(n) { primes <- rep(TRUE, n) primes[1] <- FALSE for (i in 1:sqrt(n)) { if (primes[i]) primes[seq(i^2, n, i)] <- FALSE } which(primes) } 

0.12 секунды на моем компьютере для n = 1e6

Я реализовал это в функции AllPrimesUpTo в пакете primefactr.

Я рекомендую прагмену , внедрение Дан Бернштейна в сите Аткина-Бернштейна. Это очень быстро и хорошо масштабируется для других проблем. Вам нужно будет передать данные программе, чтобы использовать ее, но я полагаю, что есть способы сделать это?

Вы также можете обманывать и использовать функцию primes() в schoolmath пакете: D

ОП попросил генерировать все простые числа ниже одного миллиарда. Все ответы, предоставленные до сих пор, либо не способны это сделать, потребуется много времени для выполнения, либо в настоящее время недоступны в R (см. Ответ от @Charles). Пакет RcppAlgos (я автор) способен генерировать запрошенный результат всего за 1 second . Он основан на сегментированном сите Эратосфена Кимом Валишем .

 library(RcppAlgos) system.time(primeSieve(10^9)) user system elapsed 1.300 0.105 1.406 

Кроме того, ниже приведена сводка пакетов (и функция sieve выше, предоставленная @John), которая может генерировать простые числа.

 library(schoolmath) library(primefactr) library(sfsmisc) library(primes) library(numbers) library(spuRs) library(randtoolbox) library(matlab) ## and 'sieve' from @John 

Прежде чем мы начнем, отметим, что проблемы, отмеченные @Henrik в школьной schoolmath все еще существуют. Заметим:

 ## 1 is NOT a prime number schoolmath::primes(start = 1, end = 20) [1] 1 2 3 5 7 11 13 17 19 ## This should return 1, however it is saying that 52 "prime" ## numbers less than 10^4 are divisible by 7.... Huuuhhh???? sum(schoolmath::primes(start = 1, end = 10^4) %% 7L == 0) [1] 52 

Дело в том, что на данный момент не используйте schoolmath для создания простых чисел (без обид автора … На самом деле, я подал вопрос с сопровождающим).

Давайте посмотрим на randtoolbox поскольку он выглядит невероятно эффективным. Заметим:

 ## the argument for get.primes is for how many prime numbers you need ## whereas most packages get all primes less than a certain number microbenchmark(priRandtoolbox = get.primes(78498), priRcppAlgos = RcppAlgos::primeSieve(10^6), unit = "relative") Unit: relative expr min lq mean median uq max neval priRandtoolbox 1.00000 1.00000 1.00000 1.00000 1.000000 1.000000 100 priRcppAlgos 19.37208 18.30095 9.897374 7.639231 7.249031 5.449076 100 

Более пристальный взгляд показывает, что это, по существу, таблица поиска (найденная в файле randtoolbox.c из исходного кода).

 #include "primes.h" void reconstruct_primes() { int i; if (primeNumber[2] == 1) for (i = 2; i < 100000; i++) primeNumber[i] = primeNumber[i-1] + 2*primeNumber[i]; } 

Где primes.h - это заголовочный файл, содержащий массив «половинок различий между простыми числами» . Таким образом, вы будете ограничены количеством элементов в этом массиве для генерации простых чисел (т. Е. Первых 100 тысяч простых чисел). Если вы работаете только с меньшими штрихами (менее 1,299,709 (т. 1,299,709 100 000- 1,299,709 премьер)), и вы работаете над проектом, который требует nth числа, randtoolbox - это путь.

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

 microbenchmark(priRcppAlgos = RcppAlgos::primeSieve(10^6), priNumbers = numbers::Primes(10^6), priSpuRs = spuRs::primesieve(c(), 2:10^6), priPrimes = primes::generate_primes(1, 10^6), priPrimefactr = primefactr::AllPrimesUpTo(10^6), priSfsmisc = sfsmisc::primes(10^6), priMatlab = matlab::primes(10^6), priJohnSieve = sieve(10^6), unit = "relative") Unit: relative expr min lq mean median uq max neval priRcppAlgos 1.000000 1.00000 1.00000 1.000000 1.00000 1.000000 100 priNumbers 21.599399 21.27664 20.17172 20.348373 20.82308 10.992780 100 priSpuRs 223.240897 231.69938 198.16347 215.520998 202.37479 59.608137 100 priPrimes 41.689864 38.43470 33.74977 35.329320 33.21983 17.323242 100 priPrimefactr 39.452661 39.77808 38.64081 37.887232 36.71392 14.549090 100 priSfsmisc 9.667778 11.16356 11.58725 10.862231 11.61987 8.990612 100 priMatlab 21.055741 21.45761 21.46455 21.053058 20.86727 15.029687 100 priJohnSieve 9.316246 10.22913 10.52325 9.825776 10.30900 8.167797 100 

Давайте проверим скорость генерации простых чисел в диапазоне:

 microbenchmark(priRcppAlgos = RcppAlgos::primeSieve(10^9, 10^9 + 10^6), priNumbers = numbers::Primes(10^9, 10^9 + 10^6), priPrimes = primes::generate_primes(10^9, 10^9 + 10^6), unit = "relative", times = 20) Unit: relative expr min lq mean median uq max neval priRcppAlgos 1.0000 1.0000 1.0000 1.0000 1.0000 1.00000 20 priNumbers 137.5877 134.2035 125.1085 133.1225 121.9784 94.93077 20 priPrimes 911.2896 877.6692 806.9694 861.4054 783.9666 568.05759 20 20 

Теперь давайте удалим условие if(n > 1e8) stop("n too large") в sieve функции, чтобы проверить, как быстро он может генерировать простые числа под миллиардом, а также функцию primes из пакета sfsmisc , поскольку они были быстрее после RcppAlgos .

 system.time(sieve(10^9)) user system elapsed 26.703 4.582 31.328 system.time(sfsmisc::primes(10^9)) user system elapsed 24.772 4.521 29.436 

Из этого видно, что RcppAlgos масштабируется намного лучше, когда n становится больше (т.е. 1.406 (см. Выше) примерно на 20-22x быстрее, тогда как для 10^6 это было всего около 10x ).

И только для хорошей меры:

 ## primes less than 10 billion system.time(tenBillion < - RcppAlgos::primeSieve(10^10)) user system elapsed 16.510 1.784 18.296 length(tenBillion) [1] 455052511 ## Warning!!!... Large object created tenBillionSize <- object.size(tenBillion) print(tenBillionSize, units = "Gb") 3.4 Gb 

Увезти

  1. Существует множество отличных пакетов для генерации простых чисел
  2. Если вы ищете скорость в целом, нет никакого соответствия RcppAlgos::primeSieve .
  3. Если вы работаете с небольшими штрихами, посмотрите не дальше, чем randtoolbox::get.primes .
  4. Если вам нужны простые числа в диапазоне, numbers пакетов, primes и RcppAlgos - это путь.
  5. Невозможно переоценить важность хорошей практики программирования (например, векторизация, использование правильных типов данных и т. Д.). Это наиболее точно продемонстрировано чистым базовым R-решением, предоставленным компанией @John. Это краткий, ясный и очень эффективный.

Вышеуказанная функция isPrime () может использовать сито (). Нужно только проверить, не разделит ли какой-нибудь из простых чисел < потолок (sqrt (x)) x без остатка. Нужно также обрабатывать 1 и 2.

 isPrime < - function(x) { div <- sieve(ceiling(sqrt(x))) (x > 1) & ((x == 2) | !any(x %% div == 0)) } 

 for (i in 2:1000) { a = (2:(i-1)) b = as.matrix(i%%a) c = colSums(b != 0) if (c == i-2) { print(i) } } 

Каждое число (i) перед (a) проверяется на список простых чисел (n), сгенерированных путем проверки числа (i-1)

Спасибо за предложения:

 prime = function(a,n){ n=c(2) i=3 while(i < =a){ for(j in n[n<=sqrt(i)]){ r=0 if (i%%j == 0){ r=1} if(r==1){break} } if(r!=1){n = c(n,i)} i=i+2 } print(n) } 
Interesting Posts

Как я могу сделать снимок с помощью своей веб-камеры в Windows 7?

Многократное использование позиционного оператора `$` для обновления вложенных массивов

HTML-форма с несколькими скрытыми элементами управления с тем же именем

Отображение сервлета Джерси / * вызывает ошибку 404 для статических ресурсов

Как запустить функцию bash_profile из файла псевдонимов desktop .command на OSX Lion?

Устанавливает ли «Mount volume в качестве съемного носителя» вероятность повреждения данных с помощью зашифрованного USB-жесткого диска TrueCrypt?

Случайный порядок столбца данных в Excel

Преобразование эпохи в «настоящую» дату / время

В регулярных выражениях, что такое обратная ссылка / обратная ссылка?

В MacBook с двойной загрузкой, используя BootCamp, переместил жесткий диск в оптический отсек, и Windows больше не загружается

Каков наилучший способ ввода числовых значений с десятичными точками?

Как использовать глобальный var для файлов в пакете?

Конкатенация диапазона со значениями между

Синхронизировать ZIP-файл PowerShell

Возможно ли слишком часто форматировать жесткий диск?

Давайте будем гением компьютера.