Advertisement
Guest User

Highly Efficient Prime Generator

a guest
Apr 30th, 2013
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. //
  2. //  main.cpp
  3. //  Pi Generator
  4. //
  5. //  Created by Nikolaj Ignatieff Schwartzbach on 2/6/13.
  6. //  Copyright (c) 2013 Nikolaj Ignatieff Schwartzbach. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <math.h>
  11. #include <time.h>
  12.  
  13. using namespace std;
  14.  
  15. int limit=0;
  16. int p=2;
  17. int nextPrime=5;
  18. void writeNumber(int ix){
  19.     int j , i = 0, k = 0;
  20.     if( ix < 0){cout << '-';ix *= -1;}
  21.     int temp = ix;
  22.     int p = 1;
  23.     while( temp > 0){temp /= 10;p *= 10;i++;}
  24.     j = i % 3;
  25.     p /= 10;
  26.     while( i > 0 ){
  27.         cout << char ((ix/p) +'0');
  28.         ix %= p;p /= 10;i--;k++;j--;
  29.         if ((k % 3 == 0 && i > 0)||(j == 0 && i > 2)){cout <<".";k = 0;}}
  30. }
  31. int main(int argc, const char * argv[])
  32. {
  33.     clock_t t1, t2;
  34.     int isPrime, i, nxtSQR, limit;
  35.     cout << "Amount of primes to find: ";
  36.     cin >> limit;
  37.     if(cin.fail()) cout << "Non-numeric input detected. Action aborted.";
  38.     cout << "Finding ";
  39.     writeNumber(limit);
  40.     cout << " primes..." << endl << endl;
  41.     int* primes = new int[limit];
  42.     primes[0]=2;
  43.     primes[1]=3;
  44.     t1 = clock();
  45.     while(p<limit){
  46.         nxtSQR = sqrt(nextPrime);
  47.         isPrime=true;
  48.         for(i=0;i<limit;i++){
  49.             if(primes[i]==0 || primes[i]>nxtSQR) break;
  50.             if(nextPrime % primes[i] == 0){isPrime=false;break;}}
  51.         if(isPrime){primes[p]=nextPrime;p++;}        nextPrime+=2;
  52.         if(nextPrime % 5 == 0)nextPrime+=2;
  53.     }
  54.     t2 = clock();
  55.     float diff = ( (float)t2 - (float)t1) / 1000000 ;
  56.     cout << "Execution Time: " << diff << " seconds.\n";
  57.     cout << "Highest prime:  ";
  58.     writeNumber(primes[limit-1]);
  59.     cout << endl;
  60.     system( "read -n 1 -s -p \"Press any key to continue...\"" );
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement