performance - son - tabla de numeros compuestos
¿El código más eficiente para los primeros 10000 números primos? (29)
Quiero imprimir los primeros 10000 números primos. ¿Alguien puede darme el código más eficiente para esto? Aclaraciones:
- No importa si su código es ineficiente para n> 10000.
- El tamaño del código no importa.
- No puede simplemente codificar los valores de ninguna manera.
Aquí el código que hice:
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;
}
Aquí está mi código que encuentra los primeros 10,000 primos en 0.049655 segundos en mi computadora portátil, los primeros 1,000,000 de primos en menos de 6 segundos y los primeros 2,000,000 en 15 segundos
Una pequeña explicación.
Este método usa 2 técnicas para encontrar el número primo
- en primer lugar, cualquier número no primo es un compuesto de múltiplos de números primos, por lo que esta prueba de código dividiendo el número de prueba por números primos más pequeños en lugar de cualquier número, esto disminuye el cálculo al menos 10 veces para un número de 4 dígitos y aún más para un número mayor
- en segundo lugar, además de dividir entre primos, solo se divide por números primos que son más pequeños o iguales a la raíz del número que se está probando, lo que reduce aún más los cálculos, esto funciona porque cualquier número que sea mayor que la raíz del número tendrá un número de contraparte que tiene que ser más pequeño que la raíz del número, pero dado que ya hemos probado todos los números más pequeños que la raíz, por lo tanto, no necesitamos molestarnos con un número mayor que la raíz del número que se está probando.
Salida de muestra para el primer número primo de 10.000
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0
https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Aquí está el código en lenguaje C, ingrese 1 y luego 10,000 para imprimir los primeros 10,000 primos.
Editar: Olvidé que esto contiene una biblioteca matemática, si estás en Windows o Visual Studio, eso debería estar bien, pero en Linux debes compilar el código usando el argumento -lm o el código puede no funcionar
Ejemplo: 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);
}
Como solo desea los primeros 10000 primos, en lugar de codificar un algoritmo complejo, le sugeriré lo siguiente
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;
}
ahora la llamada es excelente ya que la necesitas
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
Esta es una vieja pregunta, pero hay algo que todos están perdiendo ...
Para este primos, la división pequeño ensayo no es que lento ... sólo hay 25 números primos menores de 100. Con tan pocos números primos a prueba, y tan pequeños primos, podemos sacar un buen truco!
Si a es coprimo a b, entonces gcd ab = 1. Coprime. Palabra divertida Significa que no comparte ningún factor primo . Por lo tanto, podemos probar la divisibilidad por varios primos con una llamada GCD. ¿Cuántos? Bueno, el producto de los primeros 15 primos es menor que 2 ^ 64. Y el producto de los próximos 10 también es inferior a 2 ^ 64. Eso es todo lo que necesitamos. Pero ¿vale la pena?
Veamos:
check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes
a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes
Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)
Una mejora de 6 veces allí.
(
length
es forzar el cálculo de la lista. De forma predeterminada, Haskell imprime cosas de 1 carácter Unicode a la vez y, por lo tanto,
imprimir
la lista dominará el tiempo o dominará la cantidad de código real utilizada).
Por supuesto, esto se está ejecutando en GHCi, una respuesta que ejecuta código interpretado, en una computadora portátil vieja y no interpreta ninguno de estos números como
int64
s o incluso
BigInt
s, ni lo hará incluso si lo solicita (bueno,
puede
forzarlo , pero es feo y realmente no ayuda).
Está interpretando cada número allí como
cosas
generalizadas tipo
Integer
que se pueden especializar a algún tipo en particular a través de la búsqueda en el diccionario, y está atravesando una lista vinculada (que no se fusiona aquí ya que no se compila) 3 veces.
Curiosamente, la fusión manual de los dos filtros en realidad lo ralentiza en el REPL.
Vamos a compilarlo:
.../Haskell/8.6/Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total time 0.000s ( 0.004s elapsed)
Usando el informe RTS porque Windows.
Algunas líneas se recortaron porque no son relevantes: eran otros datos de GC, o medidas de solo una parte de la ejecución, y juntas suman 0.004s (o menos).
Tampoco es un plegado constante, porque Haskell en realidad no hace mucho de eso.
Si nos retiramos constantemente (
main = print 10000
), obtenemos una asignación dramáticamente menor:
...Haskell/8.6/Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total time 0.000s ( 0.001s elapsed)
Literalmente lo suficiente para cargar el tiempo de ejecución, luego descubrir que no hay nada que hacer más que imprimir un número y salir. Agreguemos factorización de rueda:
wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel
Total time 0.000s ( 0.003s elapsed)
Reduzca aproximadamente 1/3 en relación con nuestra referencia de
main = print 10000
, pero definitivamente hay espacio para una mayor optimización.
De hecho, se detuvo para realizar un GC allí, por ejemplo, mientras que con los ajustes no debería haber ningún uso del montón.
Por alguna razón, compilar para crear perfiles aquí en realidad reduce el tiempo de ejecución a 2 milisegundos:
Tue Nov 12 21:13 2019 Time and Allocation Profiling Report (Final)
Primes.exe +RTS -p -RTS
total time = 0.00 secs (2 ticks @ 1000 us, 1 processor)
total alloc = 967,120 bytes (excludes profiling overheads)
Voy a dejar esto como está por ahora, estoy bastante seguro de que el jitter aleatorio está empezando a dominar.
He escrito esto usando python, ya que recién comencé a aprenderlo, y funciona perfectamente bien.
El primer número 10.000 generado por este código es el mismo que se menciona en
http://primes.utm.edu/lists/small/10000.txt
.
Para verificar si
n
es primo o no, divide
n
entre los números de
2
a
sqrt(n)
.
Si alguno de este rango de números se divide perfectamente,
n
entonces no es primo.
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))
He estado trabajando en encontrar primos durante aproximadamente un año. Esto es lo que encontré como el más rápido:
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 segundos para llegar a 2147483629 a partir de 2.
Paso un tiempo escribiendo un programa que calcula muchos primos y este es el código que utilizo para calcular un archivo de texto que contiene los primeros 1.000.000.000 primos.
Está en alemán, pero la parte interesante es el método
calcPrimes()
.
Los primos se almacenan en una matriz llamada Primzahlen.
Recomiendo una CPU de 64 bits porque los cálculos son con enteros de 64 bits.
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);
}
}
}
Puedo darte algunos consejos, tienes que implementarlo.
- Para cada número, obtenga la mitad de ese número. Por ejemplo, para verificar 21, solo obtenga el resto dividiéndolo del rango 2-10.
- Si es un número impar, solo divídalo por un número impar, y viceversa. Tal como para 21, divida solo con 3, 5, 7, 9.
El método más eficiente que llegué hasta ahora.
Usando Sieve of Eratosthenes, el cálculo es bastante más rápido en comparación con el algoritmo de números primos "conocidos".
Al usar el pseudocódigo de su wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), puedo tener la solución en 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) toma 2s y 330ms.
NOTA : El valor puede variar según las especificaciones de hardware.
Usando el método Array.prototype.find () en Javascript. 2214,486 ms
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
@Matt: log (log (10000)) es ~ 2
Del artículo de Wikipedia (que usted citó) Sieve of Atkin :
Este tamiz calcula primos hasta N utilizando operaciones
O(N/log log N)con solo N 1/2 + o (1) bits de memoria. Eso es un poco mejor que el tamiz de Eratóstenes que usa operaciones O (N) y bits de memoria O (N 1/2 (log log N) / log N) (AOL Atkin, DJ Bernstein, 2004) . Estas complejidades computacionales asintóticas incluyen optimizaciones simples, como la factorización de la rueda y la división del cálculo en bloques más pequeños.
Dadas las complejidades computacionales asintóticas a lo largo de
O(N)
(para Eratóstenes) y
O(N/log(log(N)))
(para Atkin) no podemos decir (para pequeños
N=10_000
) qué algoritmo si se implementa será más rápido.
Achim Flammenkamp escribió en El tamiz de Eratóstenes :
citado por:
@ num1
Para intervalos mayores de aproximadamente 10 ^ 9, seguramente para aquellos> 10 ^ 10, el Tamiz de Eratóstenes es superado por el Tamiz de Atkins y Bernstein, que utiliza formas cuadráticas binarias irreducibles. Consulte su documento para obtener información de antecedentes, así como el párrafo 5 del Ph.D. de W. Galway. tesis.
Por lo tanto, para
10_000
Sieve of Eratosthenes puede ser más rápido que Sieve of Atkin.
Para responder a OP, el código es
prime_sieve.c
(citado por
num1
)
Adaptando y siguiendo desde GateKiller , aquí está la versión final que he usado.
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;
}
Básicamente es lo mismo, pero agregué la sugerencia "break on Sqrt" y cambié algunas de las variables para que me quedara mejor. (Estaba trabajando en Euler y necesitaba el número 10001)
Aquí está mi código VB 2008, que encuentra todos los primos <10,000,000 en 1 min 27 segundos en mi computadora portátil de trabajo. Omite números pares y solo busca números primos que son <el sqrt del número de prueba. Solo está diseñado para encontrar números primos de 0 a un valor 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
Aquí hay un Tamiz de Eratóstenes que escribí en PowerShell hace unos días. Tiene un parámetro para identificar la cantidad de números primos que se deben devolver.
#
# 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
}
Aquí hay una solución C ++, usando una forma de 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;
}
Tenga en cuenta que esta versión de Sieve puede calcular primos indefinidamente.
También tenga en cuenta, el TEL
deque
toma
O(1)
el tiempo para llevar a cabo
push_back
,
pop_front
y de acceso aleatorio, aunque subíndices.
La
resize
operación lleva
O(n)
tiempo, donde
n
es el número de elementos que se agregan.
Debido a cómo estamos usando esta función, podemos tratar esta es una pequeña constante.
El cuerpo del
while
bucle
my_insert
se ejecuta
O(log log n)
veces, donde
n
es igual a la variable
maybe_prime
.
Esto se debe a que la expresión de condición de la
while
evaluación se evaluará como verdadera una vez para cada factor primo de
maybe_prime
.
Consulte "
Función del divisor
" en Wikipedia.
La multiplicación por el número de veces que
my_insert
se llama muestra que debería llevar
O(n log log n)
tiempo enumerar los
n
números primos ... lo cual es, como era de esperar, la complejidad temporal que se supone que tiene el Tamiz de Eratóstenes.
Sin embargo, si bien este código es eficiente, no es el más eficiente ... Sugeriría utilizar una biblioteca especializada para la generación de primos, como primesieve . Cualquier solución verdaderamente eficiente y bien optimizada tomará más código del que cualquiera quiera escribir en .
El algoritmo de cribado mencionado por BenGoldberg merece una mirada más cercana, no solo porque es muy elegante sino también porque ocasionalmente puede ser útil en la práctica (a diferencia del Tamiz de Atkin, que es un ejercicio puramente académico).
La idea básica detrás del algoritmo de deve tamizado es utilizar un tamiz deslizante pequeño que sea lo suficientemente grande como para contener al menos un múltiplo separado para cada uno de los factores primos ''activos'' actualmente, es decir, aquellos primos cuyo cuadrado no excede el número más bajo actualmente representado por el tamiz móvil. Otra diferencia con el SoE es que el tamiz de almacenamiento almacena los factores reales en las ranuras de los compuestos, no en los booleanos.
El algoritmo extiende el tamaño de la ventana del tamiz según sea necesario, lo que resulta en un rendimiento bastante uniforme en un amplio rango hasta que el tamiz comienza a exceder la capacidad del caché L1 de la CPU de manera apreciable. El último primo que se ajusta completamente es 25,237,523 (el primo 1,579,791), lo que da una cifra aproximada aproximada para el rango operativo razonable del algoritmo.
El algoritmo es bastante simple y robusto, e incluso tiene un rendimiento en un rango mucho más amplio que un Tamiz de Eratóstenes no segmentado. Este último es mucho más rápido siempre que su tamiz se ajuste completamente en el caché, es decir, hasta 2 ^ 16 para un tamiz de probabilidades con bools de tamaño byte. Luego, su rendimiento disminuye cada vez más, aunque siempre se mantiene significativamente más rápido que el deque a pesar de la desventaja (al menos en lenguajes compilados como C / C ++, Pascal o Java / C #).
Aquí hay una representación del algoritmo de criba de decantación en C #, porque encuentro que el lenguaje, a pesar de sus muchos defectos, es mucho más práctico para la creación de prototipos de algoritmos y experimentación que el C ++ extremadamente engorroso y pedante. ( LINQPad al LINQPad : estoy usando el LINQPad gratuito que hace posible sumergirse directamente, sin todo el desorden con la configuración de proyectos, archivos MAKE, directorios o cualquier otra cosa, y me da el mismo grado de interactividad que un indicador de Python).
C # no tiene un tipo de deque explícito, pero la
List<int>
simple
List<int>
funciona lo suficientemente bien como para demostrar el algoritmo.
Nota: esta versión no utiliza una deque para los primos, porque simplemente no tiene sentido sacar sqrt (n) de n primos. ¿De qué serviría eliminar 100 primos y dejar 9900? Al menos de esta manera, todos los primos se recopilan en un vector limpio, listo para su posterior procesamiento.
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;
}
}
Aquí están las dos funciones auxiliares:
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;
}
Probablemente, la forma más fácil de entender el algoritmo es imaginarlo como un Tamiz de Eratóstenes segmentado especial con un tamaño de segmento de 1, acompañado de un área de desbordamiento donde los cebadores se detienen cuando disparan sobre el extremo del segmento.
Excepto que la celda única del segmento (también conocido como
sieve[0]
) ya ha sido tamizada cuando llegamos a ella, porque se atropelló mientras era parte del área de desbordamiento.
El número representado por
sieve[0]
se mantiene en
sieve_base
, aunque
sieve_front
o
window_base
también serían buenos nombres que permiten establecer paralelos con el código de Ben o implementaciones de tamices segmentados / en ventana.
Si
sieve[0]
contiene un valor distinto de cero, entonces ese valor es un factor de
sieve_base
, que puede reconocerse como compuesto.
Como la celda 0 es un múltiplo de ese factor, es fácil calcular su próximo salto, que es simplemente 0 más ese factor.
Si esa celda ya está ocupada por otro factor, simplemente agregamos el factor nuevamente, y así sucesivamente hasta que encontremos un múltiplo del factor donde actualmente no hay otro factor estacionado (extendiendo el tamiz si es necesario).
Esto también significa que no hay necesidad de almacenar las compensaciones de trabajo actuales de los distintos primos de un segmento al siguiente, como en un tamiz segmentado normal.
Cada vez que encontramos un factor en el
sieve[0]
, su compensación de trabajo actual es 0.
La prima actual entra en juego de la siguiente manera.
Un cebado solo puede convertirse en corriente después de su propia aparición en la secuencia (es decir, cuando se ha detectado como cebado, porque no está marcado con un factor), y seguirá siendo corriente hasta el momento exacto en que el
sieve[0]
alcance su cuadrado.
Todos los múltiplos inferiores de este primo deben haberse eliminado debido a las actividades de los primos más pequeños, al igual que en un SoE normal.
Pero ninguno de los primos más pequeños puede golpear el cuadrado, ya que el único factor del cuadrado es el primo en sí y aún no está en circulación en este punto.
Eso explica las acciones tomadas por el algoritmo en el caso
sieve_base == current_prime_squared
(por cierto,
sieve[0] == 0
).
Ahora el caso
sieve[0] == 0 && sieve_base < current_prime_squared
se explica fácilmente: significa que
sieve_base
no puede ser un múltiplo de ninguno de los primos más pequeños que el primo actual, de lo contrario, se habría marcado como compuesto.
Tampoco puedo ser un múltiplo mayor del primo actual, ya que su valor es menor que el cuadrado del primo actual.
Por lo tanto, debe ser una nueva prima.
El algoritmo obviamente está inspirado en el Tamiz de Eratóstenes, pero igualmente obviamente es muy diferente. El tamiz de Eratóstenes deriva su velocidad superior de la simplicidad de sus operaciones elementales: una sola adición de índice y una tienda para cada paso de la operación es todo lo que hace durante largos períodos de tiempo.
Aquí hay un tamiz simple y no segmentado de Eratóstenes que normalmente uso para tamizar primos de factor en el rango de ushort, es decir, hasta 2 ^ 16.
Para esta publicación, lo modifiqué para que funcione más allá de 2 ^ 16 sustituyendo
int
por
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;
}
Al tamizar los primeros 10000 primos, se excederá un caché L1 típico de 32 KiByte, pero la función sigue siendo muy rápida (fracción de milisegundo incluso en C #).
Si compara este código con el tamiz de extracción, es fácil ver que las operaciones del tamiz de extracción son mucho más complicadas, y no puede amortizar efectivamente su sobrecarga porque siempre hace el tramo más corto posible de cruces consecutivos. (exactamente un solo cruce, después de omitir todos los múltiplos que ya se han tachado).
Nota: el código C # usa
int
lugar de
uint
porque los compiladores más nuevos tienen la costumbre de generar código de calidad inferior para
uint
, probablemente para empujar a las personas hacia enteros firmados ... En la versión C ++ del código anterior, usé
unsigned
todas partes, naturalmente;
el punto de referencia tenía que estar en C ++ porque quería que se basara en un tipo de deque supuestamente adecuado (
std::deque<unsigned>
; no hubo ganancia de rendimiento al usar
unsigned short
).
Estos son los números de mi computadora portátil 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
Nota: los tiempos de C # son casi exactamente el doble de los tiempos de C ++, lo cual es bastante bueno para C # y muestra que
List<int>
no se queda atrás, incluso si se abusa como una deque.
El código de tamiz simple todavía elimina la deque del agua, a pesar de que ya está operando más allá de su rango de trabajo normal (el tamaño de caché L1 excedió en un 50%, con el almacenamiento de caché correspondiente). La parte dominante aquí es la lectura de los números primos tamizados, y esto no se ve muy afectado por el problema de caché. En cualquier caso, la función se diseñó para tamizar los factores de factores, es decir, el nivel 0 en una jerarquía de tamices de 3 niveles, y normalmente solo debe devolver unos pocos cientos de factores o un bajo número de miles. De ahí su simplicidad.
El rendimiento podría mejorarse en más de un orden de magnitud mediante el uso de un tamiz segmentado y la optimización del código para extraer los cebadores tamizados (mod 3 escalonado y desenrollado dos veces, o mod 15 y desenrollar una vez), y aún más rendimiento podría exprimirse el código mediante el uso de una rueda mod 16 o mod 30 con todos los recortes (es decir, desenrollado completo para todos los residuos). Algo así se explica en mi respuesta a Buscar número primo en primer lugar en Revisión de código, donde se discutió un problema similar. Pero es difícil ver el punto de mejorar tiempos por debajo de milisegundos para una tarea única ...
Para poner las cosas un poco en perspectiva, aquí están los tiempos de C ++ para tamizar hasta 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
Por el contrario, un tamiz segmentado en C # con algunas campanas y silbatos hace el mismo trabajo en 95 ms (no hay tiempos de C ++ disponibles, ya que en este momento solo hago desafíos de código en C #).
Las cosas pueden verse decididamente diferentes en un lenguaje interpretado como Python, donde cada operación tiene un alto costo y el sobrecarga del intérprete eclipsa todas las diferencias debido a las ramas pronosticadas frente a las predicciones erróneas u operaciones de subciclo (turno, adición) vs. , y tal vez incluso la división). Eso está destinado a erosionar la ventaja de simplicidad del Tamiz de Eratóstenes, y esto podría hacer que la solución de Deque sea un poco más atractiva.
Además, muchos de los tiempos informados por otros encuestados en este tema probablemente estén dominados por el tiempo de salida . Esa es una guerra completamente diferente, donde mi arma principal es una clase simple como esta:
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;
}
}
}
Eso toma menos de 1 ms para escribir 10000 números (ordenados). Es una clase estática porque está destinada a la inclusión textual en envíos de desafío de codificación, con un mínimo de alboroto y cero sobrecarga.
En general, descubrí que es mucho más rápido si el trabajo enfocado se realiza en lotes completos, lo que significa tamizar un cierto rango, luego extraer todos los primos en un vector / matriz, luego explotar toda la matriz, luego tamizar el siguiente rango y así sucesivamente, en lugar de mezclar todo junto. Tener funciones separadas enfocadas en tareas específicas también facilita la mezcla y combinación, permite la reutilización y facilita el desarrollo / prueba.
El siguiente código de Mathcad calculó el primer millón de primos en menos de 3 minutos.
Tenga en cuenta que esto sería utilizar dobles puntos de coma flotante para todos los números y se interpreta básicamente. Espero que la sintaxis sea clara.
El tamiz parece ser la respuesta incorrecta. El tamiz le da los números primos hasta un número N , no los primeros números primos N. Ejecute @Imran o @Andrew Szeto, y obtendrá los primos hasta N.
El tamiz podría seguir siendo utilizable si sigue probando tamices para números cada vez más grandes hasta que alcance un cierto tamaño de su conjunto de resultados, y use un almacenamiento en caché de los números ya obtenidos, pero creo que aún no sería más rápido que una solución como @ Pat''s .
En Haskell, podemos escribir casi palabra por palabra la definición matemática del tamiz de Eratóstenes, "los primos son números naturales superiores a 1 sin ningún número compuesto, donde los compuestos se encuentran por enumeración de los múltiplos de cada primo ":
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 !! 10000
es casi instantáneo.
Referencias
El código anterior se ajusta fácilmente para trabajar solo en probabilidades,
primes = 2 : 3 : minus [5,7..] (foldr (/pr -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes))
.
La complejidad del tiempo se mejora mucho (hasta un factor de
registro por
encima del óptimo) al plegarse en una estructura similar a un árbol, y la complejidad del espacio se
mejora drásticamente
por la
producción de primos en varias etapas
, en
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..]
(En Haskell, los paréntesis se usan para agrupar, una llamada a la función se indica solo por la yuxtaposición,
(:)
es un operador de
contras
para las listas y
(.)
Es un operador de composición funcional:
(f . g) x = (/y -> f (gy)) x = f (gx)
).
En python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
Esto no está estrictamente en contra de la restricción de codificación, pero se acerca terriblemente. ¿Por qué no descargar programáticamente esta lista e imprimirla en su lugar?
He adaptado el código encontrado en CodeProject para crear lo siguiente:
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 + " ");
}
}
Probar esto en mi servidor ASP.NET tardó aproximadamente 1 minuto en ejecutarse.
No es eficiente en absoluto, pero puede usar una expresión regular para probar números primos.
/^1?$|^(11+?)/1+$/
Esto prueba si, para una cadena que consiste en
k
"
1
" s,
k
no
es
primo
(es decir, si la cadena consiste en un "
1
" o cualquier número de "
1
" s que se puede expresar como un producto
n
-ary).
Recomiendo un tamiz, ya sea el Tamiz de Eratóstenes o el Tamiz de Atkin.
El tamiz o Eratóstenes es probablemente el método más intuitivo para encontrar una lista de números primos. Básicamente usted:
- Escriba una lista de números del 2 al límite que desee, digamos 1000.
- Tome el primer número que no está tachado (para la primera iteración este es 2) y tache todos los múltiplos de ese número de la lista.
- Repita el paso 2 hasta llegar al final de la lista. Todos los números que no se tachan son primos.
Obviamente, hay bastantes optimizaciones que se pueden hacer para que este algoritmo funcione más rápido, pero esta es la idea básica.
El tamiz de Atkin utiliza un enfoque similar, pero desafortunadamente no sé lo suficiente para explicárselo. Pero sí sé que el algoritmo que vinculé tarda 8 segundos en descubrir todos los números primos hasta 1000000000 en un antiguo Pentium II-350
Tamiz del código fuente de Eratóstenes: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Tamiz del código fuente de Atkin: http://cr.yp.to/primegen.html
Usando GMP, uno podría escribir lo siguiente:
#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));
}
}
En mi Macbook Pro de 2,33 GHz, se ejecuta de la siguiente manera:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
Cálculo de 1,000,000 primos en la misma computadora portátil:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP está altamente optimizado para este tipo de cosas. A menos que realmente desee comprender los algoritmos escribiendo los suyos, le recomendamos que use libGMP bajo C.
GateKiller
, ¿qué tal si agrega un
break
a eso
if
en el bucle
foreach
?
Eso aceleraría mucho las cosas porque si como 6 es divisible por 2, no necesita verificar con 3 y 5. (De todos modos, votaría su solución si tuviera suficiente reputación :-) ...)
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 + " ");
}
}
El tamiz de Atkin es probablemente lo que está buscando, su tiempo de ejecución de límite superior es O (N / log log N).
Si solo ejecuta los números 1 más y 1 menos que los múltiplos de 6, podría ser aún más rápido, ya que todos los números primos superiores a 3 están a 1 de un múltiplo de seis. Recurso para mi declaración
Tamiz de Eratóstenes es el camino a seguir, debido a su simplicidad y velocidad. Mi implementación en 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;
}
Tiempo de CPU para encontrar primos (en Pentium Dual Core E2140 1.6 GHz, usando un solo núcleo)
~ 4s para lim = 100,000,000
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();
}
}
}