Le premier numéro de calcul de plaisir

C'est un peu pire que mon tamis fait sur un 8 Mhz 8088 en turbo pascal en 1986. Mais c'était après optimisations 🙂

OriginalL'auteur

Ici est une solution rapide et simple:

• Trouver les nombres premiers de moins de 100000; 9592 ont été trouvés dans les 5 ms
• Trouver les nombres premiers inférieurs à 1 000 000; 78498 ont été trouvés dans les 20 ms
• Trouver les nombres premiers de moins de 10000000; 664579 ont été trouvés dans 143 ms
• Trouver les nombres premiers de moins de 100000000; 5761455 ont été trouvés en 2024 ms

• Trouver les nombres premiers de moins de 1000000000; 50847534 ont été trouvés dans 23839 ms

  //returns number of primes less than n
  private static int getNumberOfPrimes(final int n)
  {
      if(n < 2) 
          return 0;
      BitSet candidates = new BitSet(n - 1);
      candidates.set(0, false);
      candidates.set(1, false);
      candidates.set(2, n);
      for(int i = 2; i < n; i++)
          if(candidates.get(i))
              for(int j = i + i; j < n; j += i)
                  if(candidates.get(j) && j % i == 0)
                      candidates.set(j, false);            
      return candidates.cardinality();
  }    

OriginalL'auteur

En C#:

class Program
{
static void Main(string[] args)
{
int count = 0;
int max = 150000;
int i = 2;
DateTime start = DateTime.Now;
while (count < max)
{
if (IsPrime(i))
{
count++;
}
i++;
}
DateTime end = DateTime.Now;
Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
Console.ReadLine();
}
static bool IsPrime(int n)
{
if (n < 4)
return true;
if (n % 2 == 0)
return false;
int s = (int)Math.Sqrt(n);
for (int i = 2; i <= s; i++)
if (n % i == 0)
return false;
return true;
}
}

De sortie:

Temps Total: 2.087 secondes

OriginalL'auteur

La déclaration de la variable premier

        while (count < topPrime) {
boolean prime = true;

dans la boucle de la rendre inefficace? (Je suppose qu'il n'a pas d'importance, car je pense que Java serait d'optimiser ce)

boolean prime;        
while (count < topPrime) {
prime = true;

OriginalL'auteur

Mon prendre à l'optimisation, en évitant de trop cryptique astuces. J'utilise l'astuce donnée par I-DONNER-TERRIBLE-des CONSEILS, je le savais, et j'ai oublié... 🙂

public class Primes
{
//Original code
public static void first()
{
int topPrime = 150003;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current;
//     System.out.print(lastPrime + " "); //Checking algo is correct...
}
if (current == 2) {
current++;
} else {
current = current + 2;
}
}
System.out.println("\n-- First");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
}
//My attempt
public static void second()
{
final int wantedPrimeNb = 150000;
int count = 0;
int currentNumber = 1;
int increment = 4;
int lastPrime = 0;
long start = System.currentTimeMillis();
NEXT_TESTING_NUMBER:
while (count < wantedPrimeNb)
{
currentNumber += increment;
increment = 6 - increment;
if (currentNumber % 2 == 0) //Even number
continue;
if (currentNumber % 3 == 0) //Multiple of three
continue;
int top = (int) Math.sqrt(currentNumber) + 1;
int testingNumber = 5;
int testIncrement = 2;
do
{
if (currentNumber % testingNumber == 0)
{
continue NEXT_TESTING_NUMBER;
}
testingNumber += testIncrement;
testIncrement = 6 - testIncrement;
} while (testingNumber < top);
//If we got there, we have a prime
count++;
lastPrime = currentNumber;
//     System.out.print(lastPrime + " "); //Checking algo is correct...
}
System.out.println("\n-- Second");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double) (System.currentTimeMillis() - start) / 1000);
}
public static void main(String[] args)
{
first();
second();
}
}

Oui, j'ai utilisé une étiquette de poursuivre, première fois que j'ai essayer en Java...

Je sais que je peux sauter le calcul des premiers nombres premiers, mais ils sont bien connus, pas de point de recalculer. 🙂 Je peux coder en dur de leur sortie en cas de besoin! En outre, il ne donne pas un avantage décisif de toute façon.

Résultats:

-- La première

Dernier premier = 2015201

Temps Total = 4.281

-- Deuxième

Dernier premier = 2015201

Temps Total = 0.953

Pas mal. Pourrait être amélioré un peu, je suppose, mais trop d'optimisation peut tuer le code de bonne.

OriginalL'auteur

J'ai décidé d'essayer ce en F#, mon décent première tentative. En utilisant le Crible d'Eratosthène sur mon 2.2 Ghz Core 2 Duo, il fonctionne grâce à 2..150 000 environ 200 millisecondes. Chaque fois qu'elle appelle de l'auto, il est éliminé au courant des multiples de la liste, de sorte qu'il devient juste plus rapide au fur et à mesure. C'est un de mes premiers essais en F#, de sorte que toute les remarques constructives seront les bienvenues.

let max = 150000
let numbers = [2..max]
let rec getPrimes sieve max =
match sieve with
| [] -> sieve
| _ when sqrt(float(max)) < float sieve.[0] -> sieve
| _ -> let prime = sieve.[0]
let filtered = List.filter(fun x -> x % prime <> 0) sieve //Removes the prime as well so the recursion works correctly.
let result = getPrimes filtered max
prime::result        //The filter removes the prime so add it back to the primes result.
let timer = System.Diagnostics.Stopwatch()
timer.Start()
let r = getPrimes numbers max
timer.Stop()
printfn "Primes: %A" r
printfn "Elapsed: %d.%d" timer.Elapsed.Seconds timer.Elapsed.Milliseconds

OriginalL'auteur

Voici ma solution... c'est assez rapide... il calcule les nombres premiers entre 1 et 10 000 000 de 3 secondes sur ma machine (core i7 @ 2.93 Ghz) sur Vista64.

Ma solution est en C, mais je ne suis pas un professionnel de la C programmeur. Hésitez pas à critiquer l'algorithme et le code lui-même 🙂

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
//5MB... allocate a lot of memory at once each time we need it
#define ARRAYMULT 5242880 
//list of calculated primes
__int64* primes; 
//number of primes calculated
__int64 primeCount;
//the current size of the array
__int64 arraySize;
//Prints all of the calculated primes
void PrintPrimes()
{
__int64 i;
for(i=0; i<primeCount; i++)
{
printf("%d ", primes[i]);
}
}
//Calculates all prime numbers to max
void CalcPrime(__int64 max)
{
register __int64 i;
double square;
primes = (__int64*)malloc(sizeof(__int64) * ARRAYMULT);
primeCount = 0;
arraySize = ARRAYMULT;
//we provide the first prime because its even, and it would be convenient to start
//at an odd number so we can skip evens.
primes[0] = 2;
primeCount++;
for(i=3; i<max; i+=2)
{
int j;
square = sqrt((double)i);
//only test the current candidate against other primes.
for(j=0; j<primeCount; j++)
{
//prime divides evenly into candidate, so we have a non-prime
if(i%primes[j]==0)
break;
else
{
//if we've reached the point where the next prime is > than the square of the
//candidate, the candidate is a prime... so we can add it to the list
if(primes[j] > square)
{
//our array has run out of room, so we need to expand it
if(primeCount >= arraySize)
{
int k;
__int64* newArray = (__int64*)malloc(sizeof(__int64) * (ARRAYMULT + arraySize));
for(k=0; k<primeCount; k++)
{
newArray[k] = primes[k];
}
arraySize += ARRAYMULT;
free(primes);
primes = newArray;
}
//add the prime to the list
primes[primeCount] = i;
primeCount++;
break;
}
}
}
}
}
int main()
{
int max;
time_t t1,t2;
double elapsedTime;
printf("Enter the max number to calculate primes for:\n");
scanf_s("%d",&max);
t1 = time(0);
CalcPrime(max);
t2 = time(0);
elapsedTime = difftime(t2, t1);
printf("%d Primes found.\n", primeCount);
printf("%f seconds elapsed.\n\n",elapsedTime);
//PrintPrimes();
scanf("%d");
return 1;
}

OriginalL'auteur

@ Marque de la Rançon ne sais pas si c'est du code java

Ils vont gémir éventuellement mais j'ai voulu réécrire à l'aide de paradigme j'ai appris à avoir confiance en Java, et ils ont dit que pour avoir du plaisir, assurez-vous qu'ils comprennent que spec ne dit rien que les effets de la commande sur l'ensemble de résultats renvoyés, vous jetterait le jeu de résultats dot valeurs() pour une liste de type de donnée de mon one-off dans le bloc-notes avant de prendre une courte course

=============== commencer le code non testé ===============

package demo;
import java.util.List;
import java.util.HashSet;
class Primality
{
int current = 0;
int minValue;
private static final HashSet<Integer> resultSet = new HashSet<Integer>();
final int increment = 2;
//An obvious optimization is to use some already known work as an internal
//constant table of some kind, reducing approaches to boundary conditions.
int[] alreadyKown = 
{
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, 101, 103, 107, 109, 113, 
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541
};
//Trivial constructor.
public Primality(int minValue)
{
this.minValue = minValue;
}
List calcPrimes( int startValue )
{
//eliminate several hundred already known primes 
//by hardcoding the first few dozen - implemented 
//from prior work by J.F. Sebastian
if( startValue > this.minValue )
{
//Duh.
current = Math.abs( start );
do
{
boolean prime = true;
int index = current;
do
{
if(current % index == 0)
{
//here, current cannot be prime so break.
prime = false;
break;
}
while( --index > 0x00000000 );
//Unreachable if not prime
//Here for clarity
if ( prime )
{     
resultSet dot add ( or put or whatever it is )
new Integer ( current ) ;
}
}
while( ( current - increment ) > this.minValue );
//Sanity check
if resultSet dot size is greater that zero
{
for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
return resultSet;
}
else throw an exception ....
}

=============== fin du code non testé ===============

À l'aide de Jeux de Hachage permet de rechercher les résultats que les B-Arbres, ainsi que les résultats pourraient être empilés jusqu'à ce que la machine commence à manquer alors que le point de départ pourrait être utilisé pour un autre bloc de test == la fin d'un terme utilisé en tant que Constructeur de la valeur pour une autre course, la persistance de disque travail déjà accompli et permettant aux différentiels de feed-forward dessins. Brûlé à droite maintenant, boucle logique de l'analyse des besoins.

patch (plus ajouter sqrt) :

  if(current % 5 == 0 )
if(current % 7 == 0 )
if( ( ( ( current % 12 ) +1 ) == 0) || ( ( ( current % 12 ) -1 ) == 0) ){break;}
if( ( ( ( current % 18 ) +1 ) == 0) || ( ( ( current % 18 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 24 ) -1 ) == 0) ){break;}
if( ( ( ( current % 36 ) +1 ) == 0) || ( ( ( current % 36 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 42 ) -1 ) == 0) ){break;}
//and - new work this morning:
package demo;
/**
*
* Buncha stuff deleted for posting .... duh.
*
* @author  Author
* @version 0.2.1
*
* Note strings are base36
*/
public final class Alice extends java.util.HashSet<java.lang.String>
{
//prints 14551 so it's 14 ½ seconds to get 40,000 likely primes
//using Java built-in on amd sempron 1.8 ghz /1600 mhz front side bus 256 k L-2
public static void main(java.lang.String[] args)
{
try
{
final long start=System.currentTimeMillis();
//VM exhibits spurious 16-bit pointer behaviour somewhere after 40,000
final java.lang.Integer upperBound=new java.lang.Integer(40000);
int index = upperBound.intValue();
final java.util.HashSet<java.lang.String>hashSet
= new java.util.HashSet<java.lang.String>(upperBound.intValue());//
//Arbitraily chosen value, based on no idea where to start.
java.math.BigInteger probablePrime
= new java.math.BigInteger(16,java.security.SecureRandom.getInstance("SHA1PRNG"));
do
{
java.math.BigInteger nextProbablePrime = probablePrime.nextProbablePrime();
if(hashSet.add(new java.lang.String(nextProbablePrime.toString(Character.MAX_RADIX))))
{
probablePrime = nextProbablePrime;
if( ( index % 100 ) == 0x00000000 )
{
//System.out.println(nextProbablePrime.toString(Character.MAX_RADIX));//
continue;
}
else
{
continue;
}
}
else
{
throw new StackOverflowError(new String("hashSet.add(string) failed on iteration: "+
Integer.toString(upperBound.intValue() - index)));
}
}
while(--index > 0x00000000);
System.err.println(Long.toString( System.currentTimeMillis() - start));
}
catch(java.security.NoSuchAlgorithmException nsae)
{
//Never happen
return;
}
catch(java.lang.StackOverflowError soe)
{
//Might happen
System.out.println(soe.getMessage());//
return;
}
}
}//end class Alice

OriginalL'auteur

Voici ma contribution:

Machine: 2.4 GHz Quad-Core i7 w/8 go de RAM @ 1600MHz

Compilateur: clang++ main.cpp -O3

De référence:

Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100
Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000
Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000
Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000
Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000
Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000
Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000
Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000
Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000
Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ 

Source:

#include <iostream> //cout
#include <cmath> //sqrt
#include <ctime> //clock/CLOCKS_PER_SEC
#include <cstdlib> //malloc/free
using namespace std;
int main(int argc, const char * argv[]) {
if(argc == 1) {
cout << "Please enter a number." << "\n";
return 1;
}
long n = atol(argv[1]);
long i;
long j;
long k;
long c;
long sr;
bool * a = (bool*)malloc((size_t)n * sizeof(bool));
for(i = 2; i < n; i++) {
a[i] = true;
}
clock_t t = clock();
sr = sqrt(n);
for(i = 2; i <= sr; i++) {
if(a[i]) {
for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
a[j] = false;
}
}
}
t = clock() - t;
c = 0;
for(i = 2; i < n; i++) {
if(a[i]) {
//cout << i << " ";
c++;
}
}
cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";
free(a);
return 0;
}

Il utilise le Tamis de Erastothenes approche, j'ai optimisé autant que je peux avec mes connaissances. Des améliorations bienvenues.

OriginalL'auteur