Веселое вычисление

Ответ 1

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

Вместо этого у вас есть только попытаться до квадратного корня текущего числа.

А другой оптимизацией было то, что BP сказала с изюминкой: вместо

int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
  current++;
else
  current += 2;

использование

int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;

Это должно значительно ускорить процесс.

Редактировать:
Дополнительная оптимизация предоставлена Джо Пинедой:
Удалите переменную "top".

int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;

Если эта оптимизация действительно увеличивает скорость до Java.
Расчет квадратного корня занимает много времени по сравнению с умножением двух чисел. Однако, поскольку мы перемещаем умножение в цикл for, это делается каждый отдельный цикл. Так что это МОЖЕТ замедлить ход событий в зависимости от того, насколько быстрым является алгоритм квадратного корня в Java.

Ответ 2

Это немного хуже, чем мое сито на 8 Mhz 8088 в turbo pascal в 1986 году или около того. Но это было после оптимизаций:)

Ответ 3

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

Ответ 4

Вот быстрое и простое решение:

• Поиск простых чисел менее 100000; 9592 были найдены через 5 мс
• Поиск простых чисел менее 1000000; 78498 были найдены через 20 мс
• Поиск простых чисел менее 10000000; 664579 были найдены в 143 мс
• Поиск простых чисел менее 100000000; 5761455 были найдены в 2024 мс

• Поиск простых чисел менее 1000000000; 50847534 были найдены в 23839 мс

  //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();
  }    
  

Ответ 5

Для получения первых 150000 простых чисел в Python мы берем нас под вторым (2,4 ГГц) с использованием Sieve of Eratoshenes:

#!/usr/bin/env python
def iprimes_upto(limit):
    """Generate all prime numbers less then limit.

    http://stackoverflow.com/questions/188425/project-euler-problem#193605
    """
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

def sup_prime(n):
    """Return an integer upper bound for p(n).

       p(n) < n (log n + log log n - 1 + 1.8 log log n / log n)

       where p(n) is the n-th prime. 
       http://primes.utm.edu/howmany.shtml#2
    """
    from math import ceil, log
    assert n >= 13
    pn = n * (log(n) + log(log(n)) - 1 + 1.8 * log(log(n)) / log(n))
    return int(ceil(pn))

if __name__ == '__main__':
    import sys
    max_number_of_primes = int(sys.argv[1]) if len(sys.argv) == 2 else 150000
    primes = list(iprimes_upto(sup_prime(max_number_of_primes)))
    print("Generated %d primes" % len(primes))
    n = 100
    print("The first %d primes are %s" % (n, primes[:n]))

Пример:

$ python primes.py

Generated 153465 primes
The first 100 primes are [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]

Ответ 6

В С#:

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;
    }
}

Вывод:

Общее время: 2,087 секунды

Ответ 7

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

Я думаю, что вы можете взять этот цикл:

for (int i = 2; i < top; i++)

и сделайте так, чтобы ваша счетная переменная я переходила от 3 и только пыталась сделать mod на нечетные числа, так как все простые числа, отличные от 2, никогда не делятся на какие-либо четные числа.

Ответ 8

Повторно ли объявление переменной prime

        while (count < topPrime) {

            boolean prime = true;

внутри цикла делает его неэффективным? (Я предполагаю, что это не имеет значения, так как я думаю, что Java оптимизирует это)

boolean prime;        
while (count < topPrime) {

            prime = true;

Ответ 9

С#

Улучшение кода Aistina:

Это использует тот факт, что все простые числа больше 3 имеют вид 6n + 1 или 6n-1.

Это было примерно на 4-5% увеличение скорости с увеличением на 1 для каждого прохождения через цикл.

class Program
{       
    static void Main(string[] args)
    {
        DateTime start = DateTime.Now;

        int count = 2; //once 2 and 3

        int i = 5;
        while (count < 150000)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i += 2;

            if (IsPrime(i))
            {
                count++;
            }

            i += 4;
        }

        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;
    }
}

Ответ 10

Мое стремление к оптимизации, избегая слишком загадочных трюков. Я использую трюк, данный I-GIVE-TERRIBLE-ADVICE, который я знал и забыл...: -)

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();
  }
}

Да, я использовал помеченное продолжение, первый раз, когда я пробую их в Java...
Я знаю, что я пропускаю вычисления первых нескольких простых чисел, но они хорошо известны, нет смысла их компрометировать.:-) Я могу жестко закодировать их вывод, если это необходимо! Кроме того, он все равно не дает решающего края.

Результаты:

- Первый
Последний штрих = 2015201
Общее время = 4.281

- Второй
Последний штрих = 2015201
Общее время = 0,953

Неплохо. Возможно, немного улучшится, но слишком большая оптимизация может убить хороший код.

Ответ 11

Вы должны иметь возможность сделать внутренний цикл в два раза быстрее, только оценивая нечетные числа. Не уверен, что это действительно Java, я привык к С++, но я уверен, что он может быть адаптирован.

            if (current != 2 && current % 2 == 0)
                    prime = false;
            else {
                    for (int i = 3; i < top; i+=2) {
                            if (current % i == 0) {
                                    prime = false;
                                    break;
                            }
                    }
            }

Ответ 12

Я решил попробовать это в F #, мою первую приличную попытку. Используя сито эратосфенов на моем 2.2Ghz Core 2 Duo, он проходит через 2. 150 000 примерно за 200 миллисекунд. Каждый раз, когда он называет это сам, он устраняет текущие кратные из списка, поэтому он становится быстрее, когда он идет. Это одна из моих первых попыток в F #, поэтому любые конструктивные комментарии будут оценены.

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

Ответ 13

Бьюсь об заклад, Миллер-Рабин будет быстрее. Если вы проверяете достаточно непрерывные числа, то он становится детерминированным, но я бы даже не потрудился. Как только рандомизированный алгоритм достигает того, что его частота отказов равна вероятности того, что икота процессора вызовет неправильный результат, это уже не имеет значения.

Ответ 14

Здесь мое решение... довольно быстро... он вычисляет простые числа от 1 до 10 000 000 за 3 секунды на моей машине (ядро i7 @2,93 ГГц) на Vista64.

Мое решение в C, но я не профессиональный программист на C. Не стесняйтесь критиковать алгоритм и сам код:)

#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;
}

Ответ 15

@Mark Ransom - не уверен, что это java-код

Они будут стонать, возможно, но я хотел переписать с помощью парадигмы, которую я научился доверять Java, и сказали, что они немного повеселились, пожалуйста, убедитесь, что они понимают, что спецификация ничего не говорит о том, что заказывает эффекты в возвращаемом наборе результатов, также вы бы cast result set dot values ​​() к типу списка, заданному моим одноразовым в Блокноте, прежде чем принимать короткое поручение

=============== Непрочитанный код ===============

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 ....
      }

=============== конец непроверенного кода ===============

Использование Hash Sets позволяет искать результаты как B-Trees, поэтому результаты могут быть сложены до тех пор, пока машина не начнет сбой, тогда эта стартовая точка может быть использована для другого блока тестирования == конец одного прогона, используемого как значение конструктора для другого запуска, сохраняющегося на работе с диском, уже выполненного и позволяющего создавать дополнительные схемы подачи вперед. Сгорел прямо сейчас, логика цикла нуждается в анализе.

патч (плюс добавить 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 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

Ответ 16

Вот мой пример. Программа написана на C и занимает 50 миллисекунд на моем ноутбуке (Core 2 Duo, 1 GB Ram). Я сохраняю все рассчитанные простые числа в массиве и стараюсь делиться только до числа sqrt. Конечно, это не работает, когда нам нужно очень большое количество простых чисел (с использованием 100000000), поскольку массив становится слишком большим и дает ошибку seg.

/*Calculate the primes till TOTALPRIMES*/
#include <stdio.h>
#define TOTALPRIMES 15000

main(){
int primes[TOTALPRIMES];
int count;
int i, j, cpr;
char isPrime;

primes[0] = 2;
count = 1;

for(i = 3; count < TOTALPRIMES; i+= 2){
    isPrime = 1;

    //check divisiblity only with previous primes
    for(j = 0; j < count; j++){
        cpr = primes[j];
        if(i % cpr == 0){
            isPrime = 0;
            break;
        }
        if(cpr*cpr > i){
            break;
        }
    }
    if(isPrime == 1){
        //printf("Prime: %d\n", i);
        primes[count] = i;
        count++;
    }


}

printf("Last prime = %d\n", primes[TOTALPRIMES - 1]);
}

$ time ./a.out 
Last prime = 163841
real    0m0.045s
user    0m0.040s
sys 0m0.004s

Ответ 17

Я нашел этот код где-то на своей машине, когда начал читать эту запись в блоге о простых числах. Код находится в С#, и используемый мной алгоритм пришел из моей головы, хотя он, вероятно, где-то в Википедии.;) В любом случае, он может получить первые 150000 простых чисел примерно за 300 мс. Я обнаружил, что сумма n первых нечетных чисел равна n ^ 2. Опять же, вероятно, это доказательство где-то в Википедии. Поэтому, зная это, я могу написать алгоритм, который никогда не должен был вычислять квадратный корень, но я должен вычислить постепенно, чтобы найти простые числа. Поэтому, если вы хотите Nth prime, этот алгоритм должен будет найти (N-1) предшествующие простые числа раньше! Так оно и есть. Наслаждайтесь!

//
// Finds the n first prime numbers.
//
//count: Number of prime numbers to find.
//listPrimes: A reference to a list that will contain all n first prime if getLast is set to false.
//getLast: If true, the list will only contain the nth prime number.
//
static ulong GetPrimes(ulong count, ref IList listPrimes, bool getLast)
{
    if (count == 0)
        return 0;
    if (count == 1)
    {
        if (listPrimes != null)
        {
            if (!getLast || (count == 1))
                listPrimes.Add(2);
        }

        return count;
    }

    ulong currentSquare = 1;
    ulong nextSquare = 9;
    ulong nextSquareIndex = 3;
    ulong primesCount = 1;

    List dividers = new List();

    //Only check for odd numbers starting with 3.
    for (ulong curNumber = 3; (curNumber  (nextSquareIndex % div) == 0) == false)
                dividers.Add(nextSquareIndex);

            //Move to next square number
            currentSquare = nextSquare;

            //Skip the even dividers so take the next odd square number.
            nextSquare += (4 * (nextSquareIndex + 1));
            nextSquareIndex += 2;

            //We may continue as a square number is never a prime number for obvious reasons :).
            continue;
        }

        //Check if there is at least one divider for the current number.
        //If so, this is not a prime number.
        if (dividers.Exists(div => (curNumber % div) == 0) == false)
        {
            if (listPrimes != null)
            {
                //Unless we requested only the last prime, add it to the list of found prime numbers.
                if (!getLast || (primesCount + 1 == count))
                    listPrimes.Add(curNumber);
            }
            primesCount++;
        }
    }

    return primesCount;
}

Ответ 18

Здесь мой вклад:

Машина: 2.4GHz Quad-Core i7 w/8GB RAM @1600MHz

Компилятор: clang++ main.cpp -O3

Ориентиры:

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$ 

Источник:

#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;
}

Это использует подход "Сито эрапотенов", я оптимизировал его как можно больше, насколько мне известно. Усовершенствования приветствуются.