Google Interview Question
Country: United States
Here is my try. Is this efficient engouh?
{{
static int getNumberOfPrimes(int N) {
if (N <= 0) return 0;
if (N < 3) return N-1;
List<int> primes = new List<int>(){2};
for (int i = 3; i < N; i++)
{
var flag = true;
foreach (var num in primes)
{
if ((i % num) == 0)
{
flag = false;
break;
}
}
if (flag)
{
primes.Add(i);
}
}
return primes.Count;
}
}}
It will be wastefull for big numbers. How would you calculate the # of primes smaller than 1000000?
You will have to store 1000000 ints?
The question doesn't specifically mention storage constraints, but you might want to upvote "Storage-efficient C Sieve" anyway. :)
I think your implementation has lot more wasteful operations. Here is link for for Erasthotenes
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Maintain an ordered list of upcoming prime multiples. When n=20, your list will look like this:
(21, 3)
(21, 7)
(22, 2)
(22, 11)
(25, 5)
(26, 13)
(34, 17)
(38,19)
Pop off the top of the list, and now you know that 21 is composite. Push (24,3) on to the list:
(21, 7)
(22, 2)
(22, 11)
(24, 3)
(25, 5)
(26, 13)
(34, 17)
(38,19)
Pop off the top of the list again. 21 is a duplicate, so no new info on composites/primes here, but you can update the list:
(22, 2)
(22, 11)
(24, 3)
(25, 5)
(26, 13)
(28,7)
(34, 17)
(38,19)
Pop off (22,2) and push (24,2):
(22, 11)
(24, 2)
(24, 3)
(22, 11)
(25, 5)
(26, 13)
(28,7)
(34, 17)
(38,19)
Pop off (22,11) and push (33,11)
(24, 2)
(24, 3)
(25, 5)
(26, 13)
(28,7)
(33, 11)
(34, 17)
(38,19)
Next pop off (24,2). You know your last composite was 22, and your newest composite is 24, so you just found a prime! Now you push two values into the list:
(24, 3)
(25, 5)
(26, 2) # next multiple of 2
(26, 13)
(28,7)
(33, 11)
(34, 17)
(38,19)
(46, 23) # next multiple of 23
Hopefully you get the idea by now. An easy optimization is to only deal with odd numbers, since all even numbers are composite. When excluding evens, your list would look like this after 30:
(33, 3)
(33, 11)
(35, 5)
(35, 7)
(39, 13)
(51, 17)
(57, 19)
(69, 23)
(87, 29)
P.S. This solution is less time-efficient than a simple Sieve (although not drastically so), but it's much better in terms of storage.
yes we have to use Sieve of Eratoshtenes algo but we can discard even number as we will start from 3 so allocate space for only odd number and start from 3
int size=floor(0.5 +(n-3) +1); 0.5 for only odd number n-3 start from 3 and +1 for 2
vector<int >primes ; //store all prime number
vector<bool> is_prime(size,true); //initialize all true;
for(int i=0;i<size;++1)
{
if(is_prime[i])
{
int p=(i <<1) +3 //2i +3
for(int j=((1 *i) <<1)+6*i +3; j<size;j+=p)
is_prime[j]=false;
}
}
now traverse the is_prime vector and count the true and return the count;
Any optimal solution (i.e counting the true in is_prime vector) most welcome....
sorry i have add +1 with count before returning +1 for 2
yes we have to use Sieve of Eratoshtenes algo but we can discard even number as we will start from 3 so allocate space for only odd number and start from 3
int size=floor(0.5 +(n-3) +1); 0.5 for only odd number n-3 start from 3 and +1 for 2
vector<int >primes ; //store all prime number
vector<bool> is_prime(size,true); //initialize all true;
for(int i=0;i<size;++1)
{
if(is_prime[i])
{
int p=(i <<1) +3 //2i +3
for(int j=((1 *i) <<1)+6*i +3; j<size;j+=p)
is_prime[j]=false;
}
}
now traverse the is_prime vector and count the true and return the count +1; +1 for 2 .
Any optimal solution (i.e counting the true in is_prime vector) most welcome....
Storage-efficient C Sieve.
This code conserves memory (for large N) by applying the sieve to only 1000 numbers at a time. It also skips even numbers.
#include <stdlib.h>
#include <stdio.h>
struct prime {
int n;
int max_multiple;
};
void sieve_out_multiples(
int *sieve,
struct prime *primes,
int i,
int n_start,
int n_end)
{
int offset;
while (primes[i].max_multiple < n_end) {
offset = (primes[i].max_multiple - n_start) / 2;
sieve[offset] = 1;
primes[i].max_multiple += 2 * primes[i].n;
}
}
int count_odd_primes(n) {
if (n % 2 == 0) --n;
int chunk_size = 1000; // number of odds
int n_start = 3;
int n_end = n_start + 2 * chunk_size;
if (n_end > n+2) n_end = n+2;
int cnt = 0;
chunk_size = (n_end - n_start) / 2;
int alloc_size = chunk_size; // enough to get started
struct prime *primes = malloc(alloc_size * sizeof(*primes));
int *sieve = malloc(chunk_size * sizeof(int));
int i;
while (n_start <= n) {
n_end = n_start + 2 * chunk_size;
if (n_end > n+2) n_end = n+2;
chunk_size = (n_end - n_start) / 2;
for (i = 0; i < chunk_size; ++i) {
sieve[i] = 0;
}
// mark all composities from primes so far
for (i = 0; i < cnt; ++i) {
sieve_out_multiples(sieve, primes, i, n_start, n_end);
}
for (i = n_start; i < n_end; i += 2) {
int offset = (i - n_start) / 2;
if (sieve[offset] == 0) {
// we found a prime!
// printf("prime %d\n", i);
if (cnt >= alloc_size) {
alloc_size += chunk_size / 2 + 1;
primes = realloc(primes, alloc_size * sizeof(*primes));
}
primes[cnt].n = i;
primes[cnt].max_multiple = 3 * i;
sieve_out_multiples(sieve, primes, cnt, n_start, n_end);
++cnt;
}
}
n_start = n_end;
if (n_start % 2 == 0) ++n_start;
}
return cnt;
}
int count_primes(int n) {
if (n <= 1) return 0;
if (n == 2) return 1;
return count_odd_primes(n) + 1;
}
int main(int argc, char **argv) {
printf("%d\n", count_primes(100));
printf("%d\n", count_primes(1000000));
return 0;
}
int primeNumcounter(int n){
if(n == 0){
if( (i%primeN) == 0 ){
isPrime=false;
break;
}
return 0;
}
if(n ==1){
return 1;
}
Map<int,int> numMap=new LinkedHashMap<>();
numMap.put(1,1);
for(int i=2;i<n;i++){
boolean isPrime=true;
for(int primeN : numMap.keySet()){
}
if(isPrime){
numMap.put(i,i);
}
return numMap.size();
}
ops the above comment was pasted wrong,
that's what I wanted to write:
int primeNumcounter(int n){
if(n == 0){
return 0;
}
if(n ==1){
return 1;
}
Map<int,int> numMap=new LinkedHashMap<>();
for(int i = 2 ; i < n ; i++){
boolean isPrime = true;
for(int primeN : numMap.keySet()){
if( (i%primeN) == 0 ){
isPrime = false;
break;
}
}
if(isPrime){
numMap.put(i,i);
}
return (numMap.size()+1);
}
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main(int argc, char* argv[]){
int N = atoi(argv[1]);
vector<bool> flags(N,true);
for(int i=2;i<=sqrt(N);i++){
if(flags[i-1]==true){
for(int j=i*i;j<=N;){
flags[j-1]=false;
j+=i;
}//inner for
}//if
}//outer for
int count=0;
for(int ii=1;ii<flags.size();ii++)
{
if(flags[ii]==true) count++;
}
cout<<count<<endl;
return 0;
}
0:56#hepc1 ./a.out 100
25
0:56#hepc1
0:56#hepc1 ./a.out 1000000
78498
0 1 2 3 4 5 6 7 8
6 7 8 9 1 2 3 4 5
^ ^ ^
^ ^ ^
^ ^ ^
^ ^
int find_turning_point(int *a, int n) {
int start = 0;
int end = n – 1;
while (start < end) {
if (a[start] <= a[end]) {
return end;
}
int mid = (start + end) / 2;
if (a[start] > a[mid]) {
end = mid;
} else {
start = mid;
}
}
return start;
}
int bsearch(int *a, int n, int key, bool ascend) {
int start = 0;
int end = n – 1;
while (start < end) {
int mid = (start + end) / 2;
if (a[mid] == key) {
return mid;
}
if (a[mid] < key && ascend) {
start = mid +1;
} else {
end = mid – 1;
}
}
return -1;
}
int rotate_search(int *a, int n, int key)
{
int rotate_pos = find_turning_point(a, n);
int pos = bsearch(a, rotate_pos);
if (pos != -1) return pos;
pos = bsearch(a + rotate_pos, n – rotate_pos);
if (pos == -1) return -1;
return pos + rotate_pos;
}
class PrimeNumbers
{
private:
int *primes = NULL;
int capacity = 0;
int n = 0;
int max_query = 0;
private:
void PrepareTill(int num) {
if (max_query >= num) {
return;
}
max_query = num;
if (primes == NULL) {
capacity = 10;
primes = malloc(sizeof(int) * capacity);
primes[n++] = 2;
primes[n++] = 3;
}
for (I = primes[n-1]; i<= num; i+=2)
bool is_prime = true;
for (j = 1; j <= sqrt(i); ++j) {
if (I % primes[j] == 0) {
is_prime = false;
break;
}
}
if (is_prime) {
if (n == capacity) {
capacity *= 2;
realloc(primes, sizeof(int) * capacity);
}
primes[n++] = I;
}
}
}
public:
int GetPrimeTill(int num) {
PrepareTill(num);
int I = -1; // a[i] <= key;
int j = n; // a[j] > key;
while (j – I > 1) {
int mid = (i+j)/2;
if (mid > num) {
j = mid;
} else {
I = mid;
}
}
return i;
}
};
Use Sieve of Erasthotenes
- alex February 22, 2013