Created
December 31, 2017 08:08
Star
You must be signed in to star a gist
Sieve of Erathostenes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <fstream> | |
typedef unsigned long ulong; | |
typedef unsigned int uint; | |
namespace Erathostenes { | |
ulong getCount(ulong n) { | |
ulong i,j; | |
bool isPrime[ n + 1 ]; | |
for(i = 2; i <= n; ++i) isPrime[ i ] = true; | |
ulong totalPrimes = n - 1; | |
for(i = 2; i * i <= n; ++i) { | |
if( isPrime[ i ] ) { | |
j = 2; | |
while( i * j <= n ) { | |
ulong multiple = i * j; | |
if( isPrime[ multiple ] ) totalPrimes--; | |
isPrime[ multiple ] = false; | |
j++; | |
} | |
} | |
} | |
return totalPrimes; | |
} | |
}; | |
using namespace std; | |
using namespace Erathostenes; | |
int main() { | |
const char *inFile = "ciur.in"; | |
const char *outFile = "ciur.out"; | |
ifstream fin( inFile ); | |
ofstream fout( outFile ); | |
if(!fin || !fout) { | |
cerr<<"Error opening one of "<<inFile<<" or "<<outFile<<endl; | |
return -1; | |
} | |
ulong n; | |
fin>>n; | |
fout<<getCount( n ); | |
return(0); | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment