# Primes

By: a guest on Dec 25th, 2011  |  syntax: C++  |  size: 3.22 KB  |  views: 45  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #include <time.h>
2. #include <iostream>
3. #include <vector>
4. #include <math.h>
5. using namespace std;
6.
7. const int maxnum=100000;
8. vector<int> primes1;
9. vector<int> primes2;
10. vector<int> primes3;
11.
12. void Primev1();
13. void Primev2();
14. void Primev3();
15.
16. int main()
17. {
18.     cout<<"Calculating Primes...PSketchy's code with uberdev's  correction"<<endl;
19.     Primev1();
20.     cout << "Press enter to continue."<<endl;
21.     cin.get();
22.     cout<<"Calculating Primes...Yojay's optimizations + only checking for divisility to sqrt(i)"<<endl;
23.     Primev2();
24.     cout << "Press enter to continue."<<endl;
25.     cin.get();
26.     cout<<"Calculating Primes...Only checking based on previous primes / up to sqrt(i)"<<endl;
27.     Primev3();
28.
29.     return 0;
30. }
31. void Primev1()
32. {
33.     clock_t start, end;
34.     start = clock();
35.
36.     for (int i = 2; i <= maxnum; i++)
37.     {
38.         bool isPrime = true;
39.         for (int n = 2; n < i; n++)
40.         {
41.             if (i%n == 0)
42.             {
43.                 // i is divisible by n with no remainder, so it's not a prime
44.                 isPrime = false;
45.                 break;
46.             }
47.         }
48.         if (isPrime)
49.         {
50.             primes1.push_back(i);
51.             //cout<< "prime:  " << i << endl;
52.         }
53.     }
54.
55.     end = clock();
56.     cout << "Primes found:"<< primes1.size()<<endl;
57.     cout << "Time required for execution: "
58.     << (double)(end-start)/CLOCKS_PER_SEC
59.     << " seconds." << "\n\n";
60. }
61. void Primev2()
62. {
63.     clock_t start, end;
64.     start = clock();
65.     primes2.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
66.     //cout<< "prime:  " << 2 << endl;
67.
68.     for (int i = 3; i <= maxnum; i+=2)
69.     {
70.         bool isPrime = true;
71.
72.         for (int n = 2; n <= sqrt(i); n++)
73.         {
74.             if (i%n == 0)
75.             {
76.                 // i is divisible by n with no remainder, so it's not a prime
77.                 isPrime = false;
78.                 break;
79.             }
80.         }
81.         if (isPrime)
82.         {
83.             primes2.push_back(i);
84.             //cout<< "prime:  " << i << endl;
85.         }
86.     }
87.
88.
89.     end = clock();
90.     cout << "Primes found:"<< primes2.size()<<endl;
91.     cout << "Time required for execution: "
92.     << (double)(end-start)/CLOCKS_PER_SEC
93.     << " seconds." << "\n\n";
94. }
95. void Primev3()
96. {
97.     clock_t start, end;
98.     start = clock();
99.     primes3.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
100.     //cout<< "prime:  " << 2 << endl;
101.
102.     for (int i = 3; i <= maxnum; i+=2)
103.     {
104.         bool isPrime = true;
105.         for (int j=0; j<primes3.size(); j++)
106.         {
107.             if(primes3[j]>sqrt(i))
108.                 break;
109.             if(i%primes3[j]==0)
110.             {
111.                 // i is divisible by n with no remainder, so it's not a prime
112.                 isPrime = false;
113.                 break;
114.             }
115.         }
116.         if (isPrime)
117.         {
118.             primes3.push_back(i);
119.             //cout<< "prime:  " << i << endl;
120.         }
121.     }
122.
123.
124.     end = clock();
125.     cout << "Primes found:"<< primes3.size()<<endl;
126.     cout << "Time required for execution: "
127.     << (double)(end-start)/CLOCKS_PER_SEC
128.     << " seconds." << "\n\n";
129. }
clone this paste RAW Paste Data
Top