## Amazon Interview Question Software Engineer / Developers

• 0

Write a program for prime numbers? improve the number of divisions that you are performing from all the numbers from 1 to that number to some less numbers. improve by seeing if you can decrease the loop from n to some lesser number.

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

If a number is divisible by a number less than itself, it is divisible by a number less than or equal to (int)Math.sqrt(n). Can you see why?

Comment hidden because of low score. Click to expand.
0

u can tweak it further by saying the composite number will be divisible by a prime<=sqrt(n).sth like blw to find 1st n primes

``````int primes[n]
boolean isPrime
primes[0]=2,primes[1]=3
i=5
while primes[n-1]!=0
isPrime=true
for k=1 to n-2
if primes[k]>sqrt(i)
break
else if i%primes[k]==0
isPrime=false
break
if(isPrime)
primes[k+1]=i
i+=2``````

Comment hidden because of low score. Click to expand.
0

Sure, at least if you're willing to use extra space to store those primes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Run the loop from 1 to n/2

Comment hidden because of low score. Click to expand.
0

and check only for odd numbers

Comment hidden because of low score. Click to expand.
0

and check only for odd numbers

Comment hidden because of low score. Click to expand.
0

Here the initial case is 1 to n, little bit improved is 1 to n/2 but we have to use from 2 to sqrt(n)

Comment hidden because of low score. Click to expand.
0

We only need to check for all prime number between 1 and sqrt(n).

Comment hidden because of low score. Click to expand.
0

Nani's solution is probably the most optimal for finding if a single no. is prime or not. To generate a series of primes we can apply a sieve.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Exclude cases:
1. last digit is: 0,2,4,6,8,5
2. check special cases for divisibility of 3 (and 7, 11 if u want)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Cant we divide it only by n/2, n/3, n/4, .... to see if its prime or not? Its not primse if the operation returns an integer other than 1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

For a given range of number say 1 to n we can check for primeness in the following
ie isPrime(int n)
1. if number is 1 or if n % 2 == 0 (if a number is even )then return false
2. use the axiom that if n has divisor from 1<d < n then it has divisor 1< do < sqrt(n)

``````isPrime(int n )
{
if ( (n ==1) || (n %2 ) == 0 )
return false;

if(n ==2 )
return true;

for(int i=3; i<=(int)sqrt.(n) ; i++)
if(n %i ==0)
return false;

return true;

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.