Herr Deng桑的教學blog: C++利用篩法算到10^9有幾個質數

2017年6月13日星期二

C++利用篩法算到10^9有幾個質數

26 則留言:

B10333086 陳晏堂提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
#include <vector> //
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)//
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool>& isPrime, int n, vector<int>& prime)//
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
count++;
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime( n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");; 2017年6月13日上午9:59
B10333064王韻菱提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
#include <vector>
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool>& isPrime, int n, vector<int>& prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime( n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:02
B10333106 劉郁芃提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
#include <vector>>
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool>& isPrime, int n, vector<int>& prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime(n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:03
B10333107-曾詠浩提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime(n + 1,1);
cout<<isPrime.max_size()<<endl;
//memset(isPrime, 1, n + 1);
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:04
B10333097胡聖恩提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool>& isPrime, int n, vector<int> prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime(n + 1,1);
cout<<isPrime.max_size()<<endl;

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:05
b10333080王育文提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool> & isPrime, int n, vector<int> prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime(n + 1,1);
cout<<isPrime.max_size()<<endl;

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:06
B10333094 提到...: #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector &prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime(n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:06
B10333055 翁恩義提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <vector>
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool>& isPrime, int n, vector<int> prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime(n+1, 1);
cout<<isPrime.max_size()<<endl;

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:07
B10333079 葉禮魁提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
using namespace std;

void Eratosthenes_sieve(vector<bool> & isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool> & isPrime, int n, vector<int> prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime(n + 1,1);
cout<<isPrime.max_size()<<endl;
// memset(isPrime, 1, n + 1);
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:08
B10333053 梁竣翔提到...: #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector& prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime( n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:31
b10233032 謝翔宇提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime(n+1, 1);
cout<<isPrime.max_size()<<endl;

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午10:38
B10333072 黃玟茜提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime(n + 1,1);
cout<; 2017年6月13日上午10:42
b10133187 楊鈞文提到...: #include
#include
#include
#include
#include
#include
#include
#include
#include //
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)//
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector& prime)//
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
count++;
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime( n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");; 2017年6月13日上午10:44
b10133187 楊鈞文提到...: #include
#include
#include
#include
#include
#include
#include
#include
#include //
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)//
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector& prime)//
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
count++;
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime( n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");; 2017年6月13日上午10:45
B10333072 黃玟茜提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime(n + 1,1);
cout<; 2017年6月13日上午10:45
b10133187 楊鈞文提到...: #include
#include
#include
#include
#include
#include
#include
#include
#include //
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)//
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector& prime)//
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
count++;
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime( n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");; 2017年6月13日上午10:47
b10233032 謝翔宇提到...: #include
#include
#include
#include
#include
#include
#include
#include
#include //
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)//
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector& prime)//
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
count++;
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime( n+1,1);

Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");; 2017年6月13日上午10:49
B10333027 毛冠霖提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime (n+1, 1) ;
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:07
b10333083周琬芸提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
#include<vector>
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool>& isPrime, int n, vector<int> &prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
count ++;
// prime[count++]=i;
// ff << i << endl; //
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;

vector<bool> isPrime( n+1,1);
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:07
b10433038詹恭煒提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime (n+1, 1) ;
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:09
b10433053謝肇安提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime (n+1, 1) ;
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:09
b10433193林佩縈提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime (n+1, 1) ;
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:10
b10433194謝旻君提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime (n+1, 1) ;
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:10
B10333063羅胤銓提到...: #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include <ctime>
using namespace std;

void Eratosthenes_sieve(vector<bool>& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector<bool> isPrime, int n, vector<int> prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
count++;
// prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e8;
cout << n << endl;
vector<int> prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector<bool> isPrime( n+1,1);
cout<<isPrime.max_size()<<endl;
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:13
B10333005 陳於農提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime(n + 1,1);
cout<<isPrime.max_size()<<endl;
//memset(isPrime, 1, n + 1);
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日上午11:41
B10333070 徐承瑋提到...: #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

void Eratosthenes_sieve(vector& isPrime, int n)
{
isPrime[1] = 0;
int n_sqrt = (int)(sqrt(n));
for (int i = 2; i <= n_sqrt; i++)
{
if (isPrime[i])
for (int j = i*i; j <= n; j += i)
isPrime[j] = 0;
}
}

void listPrime(vector& isPrime, int n, vector prime)
{
fstream ff("prime.csv", ios::out);
int count = 0;
for (int i = 1; i <= n; i++)
if (isPrime[i])
{
prime[count++]=i;
// ff << i << endl;
}
ff << "Prime_Pi=# of primes=" << count << endl;
cout<< "Prime_Pi=# of primes=" << count << endl;
}

int main()
{
cout << "Find the primes below the integer n:";
int n = (int)1e9;
cout << n << endl;
vector prime((int)(1.125*n / log(n)+1.5));//Use Chebyshev's prime theorem
int s = clock(), e;
vector isPrime(n + 1,1);
cout<<isPrime.max_size()<<endl;
//memset(isPrime, 1, n + 1);
Eratosthenes_sieve(isPrime, n);
e = clock() - s;
cout <<(double) e /CLOCKS_PER_SEC<< " sec\n";
listPrime(isPrime, n, prime);
system("Pause");
return 0;
}; 2017年6月13日下午4:08

張貼留言

訂閱：張貼留言 (Atom)

Herr Deng桑的教學blog

網頁

herrDeng網內搜尋

Ads

2017年6月13日星期二

C++利用篩法算到10^9有幾個質數

26 則留言:

熱門文章

DengSir7 Google Display

programming

網頁

herrDeng網內搜尋

Ads

2017年6月13日 星期二

C++利用篩法算到10^9有幾個質數

26 則留言:

熱門文章

DengSir7 Google Display

programming

2017年6月13日星期二