So i got the idea to make a prime number program that outputs the prime numbers from 0 to whatever limit the user inputs. I didn't manage to make the program calculate from 0 to the limit, so i made it go from 2 and up(i'm a noob coder).
So i bring a 'challenge' to the people on this forum, can you modify my code to make it do less calculations to find all the primes, or make your own with other rules for primes (i dont know any other at the top of my head other than throw all even numbers ,except 2, in the trash without 'testing' them)
who can make the most effective ? :)
with this program i managed to find all primes from 2 to
10 with 16 calculations
100 with 1134 calculations
1000 with 78023 calculations
10000 with 5775224 calculations
100000 with 455189151 calculations
1000000 with -1087379171 calculations (too many for int i guess)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
#include <iostream>
using namespace std;
int main()
{
int limit;
int i=2;
int j;
int k;
int calculations=0;
cout<<"Lets search for primes ! How far shall we go?"<< endl;
cin>>limit;
while(i<=limit)
{
if(i==2){ cout<<i<< endl; calculations ++; goto end;}
else
{
j=2;
k=0;
}
while(j!=i && j!=1)
{
if (i%j==0)
{
calculations ++;
goto end;
}
calculations++;
j++;
}
cout<<i<< endl;
end:
i++;
}
cout<<"We found all the primes! It took "<<calculations<<" calculations to find all the primes from 2 to "<<limit<<"!"<< endl;
return 0;
}
| |