Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Copyright (c) 2013 xerpi
- */
- #include <iostream>
- #include <vector>
- #include <cmath>
- using namespace std;
- const int MAX_N = 10000001;
- void build_sieve(vector<bool>& sieve);
- int main()
- {
- vector<bool> sieve(MAX_N);
- build_sieve(sieve);
- int n;
- while (cin >> n) {
- if (sieve[n])
- cout << n << " is prime" << endl;
- else
- cout << n << " is not prime" << endl;
- }
- }
- void build_sieve(vector<bool>& sieve)
- {
- int size = sieve.size();
- sieve[0] = false;
- sieve[1] = false;
- for (int i = 2; i < size; ++i) {
- sieve[i] = true;
- }
- int limit = sqrt(size);
- for (int i = 2; i < limit; ++i) {
- if (sieve[i]) {
- for (int j = 2*i; j < size; j+=i) {
- sieve[j] = false;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement