Advertisement
Rochet2

Prime problem ~ Optimized

Nov 14th, 2012
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include "stdafx.h"
  2. #include <stdio.h>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. #define PRIMETOFIND     1000 // how manyeth prime to find?
  7.  
  8. int main()
  9. {
  10.     unsigned int prime = 2; // last found prime (first prime is 2)
  11.     unsigned int count = 1; // prime counter (first prime hardcoded to be 2, skipping)
  12.     unsigned int number = 3; // start number (skipping 2 again)
  13.     while(count < PRIMETOFIND)
  14.     {
  15.         bool isprime = true;
  16.         for(unsigned int i = 3; i <= sqrt((long double)number); i+=2) // optimized to only check until square root of the current value and skipping even values
  17.         {
  18.             if(number % i == 0)
  19.             {
  20.                 isprime = false;
  21.                 break;
  22.             }
  23.         }
  24.         if(isprime)
  25.         {
  26.             prime = number;
  27.             count++;
  28.         }
  29.         number += 2; // optimized to skip even numbers
  30.     }
  31.     cout << count << "th prime is " << prime << endl;
  32.     cin.get(); // pausing the console
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement