Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- vector<int> primes;
- void SieveOfEratosthenes(int n)
- {
- // Create a boolean array "prime[0..n]" and initialize
- // all entries it as true. A value in prime[i] will
- // finally be false if i is Not a prime, else true.
- bool prime[n+1];
- memset(prime, true, sizeof(prime));
- for (int p=2; p*p<=n; p++)
- {
- // If prime[p] is not changed, then it is a prime
- if (prime[p] == true)
- {
- // Update all multiples of p greater than or
- // equal to the square of it
- // numbers which are multiple of p and are
- // less than p^2 are already been marked.
- for (int i=p*p; i<=n; i += p)
- prime[i] = false;
- }
- }
- // Print all prime numbers
- for (int p=2; p<=n; p++)
- if (prime[p])
- primes.push_back(p);
- }
- int binarySearch(vector<int> arr, int l, int r, int x)
- {
- if (r >= l) {
- int mid = l + (r - l) / 2;
- // If the element is present at the middle
- // itself
- if (arr[mid] == x)
- return mid;
- // If element is smaller than mid, then
- // it can only be present in left subarray
- if (arr[mid] > x)
- return binarySearch(arr, l, mid - 1, x);
- // Else the element can only be present
- // in right subarray
- return binarySearch(arr, mid + 1, r, x);
- }
- // We reach here when element is not
- // present in array
- return -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement