Amazon Interview Question
Software Engineer / DevelopersYep.
We can make a 100-length bit array.
Then iterate as follows:
Do a separate iteration over 4,6,8, etc and flip all bits at those indices.
For index from 3 to root-of-100 (i.e. 10):
If bit at index not equal to 1:
Turn to 1 bits at (index+2*index*k), where k=1,2,3,...
(e.g. for index=3, you flip 9,15,21, etc; skip even numbers)
import java.lang;
public static void Main(String[] args)
{
int [] intArray = new int[101];
for(int i=0;i<intArray.length ;i++)
{
intArray[i]=1;
}
for(int i = 2;i<101;i++)
{
int count =2;
while(count<101)
{
if(count != i)
{
if((count%i)==0)
{
intArray[count] =0;
}// end If
count++;
}// end if
}// end While
}// end for
for(int i = 0; i <intArray.length;i++)
{
if(intArray[i] == 1)
System.out.println(" values which are prime numbers:" + intArray[i]);
} // end for
}// end Main
Order of O(^2).
Please provide a feedback and a better one if possible.
Thanks
AB
import java.lang;
public static void Main(String[] args)
{
int [] intArray = new int[101];
for(int i=0;i<intArray.length ;i++)
{
intArray[i]=1;
}
for(int i = 2;i<101;i++)
{
int count =2;
while(count<101)
{
if(count != i)
{
if((count%i)==0)
{
intArray[count] =0;
}// end If
count++;
}// end if
}// end While
}// end for
for(int i = 0; i <intArray.length;i++)
{
if(intArray[i] == 1)
System.out.println(" values which are prime numbers:" + intArray[i]);
} // end for
}// end Main
Order of O(^2).
Please provide a feedback and a better one if possible.
Thanks
AB
I quickly came up with this (I feel it is correct, but u never know!)
1. Check only odd numbers.
2. For those numbers, check if the number is divisible by 3, 5 or 7.
3. If the number obeys the above 2 conditions, it is not prime, else prime.
Cute. This looks right. But a hardcoded version beats this.
Suppose some composite odd number k <= 100 is not divisible by 3,5, or 7.
Let k = a*b where a is a prime.
a must be >= 11. Also, since b is not divisible by 3,5, or 7 and is odd, b >= 11 also. This k >= 121, not possible.
I dont get it.. why must a be >=11? isn't 1,2,3,5,7 a few prime numbers less than 11?
it could be 5. 55 is an odd number, and is NOT prime.. Besides hard-coding is barely an algorithmic solution.
Further, i don't think using such a brute force mechanism is going to be a greatly intelligent idea at all, where u find all odd numbers that are not divisible by 3,5,7.
ok.. sorry 1 is not a prime number, or it is.. lets keep away from that discussion. Lets just say its not. I take 1 back.
What are you talking about?
What I wrote tries to prove that the algorithm given by Anonymous on May 28th (checking an odd number for divisibility by 3,5,7) is correct.
You can keep a boolean array range from 0-100 (call it prime). Make all entries in the array as true.
We know that 0,1 are not prime. So prime[0] and prime[1] = false.
Now starting from 2 - cancel out all factors of 2,which means prime[4],prime[6] and so on make it as (false). Once thats done, go to the next entry in prime which is true;i.e 3.
boolean[] primeArray = new boolean[n + 1];
Arrays.fill(primeArray, true);
int range = (int)Math.sqrt(n);
primeArray[0] = false;
primeArray[1] = false;
for (int count = 2; count <= range; count++)
{
if (primeArray[count])
{
for (int countFactors = count*count; countFactors<=n; countFactors = countFactors + count)
primeArray[countFactors] = false;
}
}
suppose u have number 'n', to check if it is prime, what if we check if it is divisible by a prime number less than n.
if it is divisible, then it is composite, else it is prime.
example -> n = 17
so u will check if 7 gives a remainder with 2,3,5,7,11 or 13. it doesnt hence, it is prime.
suppose n = 18. try again with 2,3,5,7,11,13,17. it is divisible by 2 and 3. hence, composite.
thus, we need to maintain a list of all prime numbers encountered below n.
Here's Python:
def sieve_primes(N):
"""Find all primes <= N using the sieve of Eratostenes"""
is_prime = 2*[False] + (N-1)*[True] # 0,1,2,3 ...
primes = []
p = 1
while 1:
try:
p = (p+1) + is_prime[(p+1):].index(True)
except ValueError:
break # no more primes in range
primes.append(p)
for i in range(2*p,N+1,p):
is_prime[i] = False
return primes
print(sieve_primes(100))
Sieve of Eratosthenes is a much better solution for a problem where you have to find primes in 1-N. For 1-100, you will only need 8 iterations to find all primes.
- SG October 20, 2008See: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes