Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <time.h>
- #include <iostream>
- #include <vector>
- #include <math.h>
- using namespace std;
- const int maxnum=100000;
- vector<int> primes1;
- vector<int> primes2;
- vector<int> primes3;
- void Primev1();
- void Primev2();
- void Primev3();
- int main()
- {
- cout<<"Calculating Primes...PSketchy's code with uberdev's correction"<<endl;
- Primev1();
- cout << "Press enter to continue."<<endl;
- cin.get();
- cout<<"Calculating Primes...Yojay's optimizations + only checking for divisility to sqrt(i)"<<endl;
- Primev2();
- cout << "Press enter to continue."<<endl;
- cin.get();
- cout<<"Calculating Primes...Only checking based on previous primes / up to sqrt(i)"<<endl;
- Primev3();
- return 0;
- }
- void Primev1()
- {
- clock_t start, end;
- start = clock();
- for (int i = 2; i <= maxnum; i++)
- {
- bool isPrime = true;
- for (int n = 2; n < i; n++)
- {
- if (i%n == 0)
- {
- // i is divisible by n with no remainder, so it's not a prime
- isPrime = false;
- break;
- }
- }
- if (isPrime)
- {
- primes1.push_back(i);
- //cout<< "prime: " << i << endl;
- }
- }
- end = clock();
- cout << "Primes found:"<< primes1.size()<<endl;
- cout << "Time required for execution: "
- << (double)(end-start)/CLOCKS_PER_SEC
- << " seconds." << "\n\n";
- }
- void Primev2()
- {
- clock_t start, end;
- start = clock();
- primes2.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
- //cout<< "prime: " << 2 << endl;
- for (int i = 3; i <= maxnum; i+=2)
- {
- bool isPrime = true;
- for (int n = 2; n <= sqrt(i); n++)
- {
- if (i%n == 0)
- {
- // i is divisible by n with no remainder, so it's not a prime
- isPrime = false;
- break;
- }
- }
- if (isPrime)
- {
- primes2.push_back(i);
- //cout<< "prime: " << i << endl;
- }
- }
- end = clock();
- cout << "Primes found:"<< primes2.size()<<endl;
- cout << "Time required for execution: "
- << (double)(end-start)/CLOCKS_PER_SEC
- << " seconds." << "\n\n";
- }
- void Primev3()
- {
- clock_t start, end;
- start = clock();
- primes3.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
- //cout<< "prime: " << 2 << endl;
- for (int i = 3; i <= maxnum; i+=2)
- {
- bool isPrime = true;
- for (int j=0; j<primes3.size(); j++)
- {
- if(primes3[j]>sqrt(i))
- break;
- if(i%primes3[j]==0)
- {
- // i is divisible by n with no remainder, so it's not a prime
- isPrime = false;
- break;
- }
- }
- if (isPrime)
- {
- primes3.push_back(i);
- //cout<< "prime: " << i << endl;
- }
- }
- end = clock();
- cout << "Primes found:"<< primes3.size()<<endl;
- cout << "Time required for execution: "
- << (double)(end-start)/CLOCKS_PER_SEC
- << " seconds." << "\n\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement