Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
#include "stdio.h"
#define bool int
#define TRUE 1
#define FALSE 0
bool isPrimNumber(int k)
{
for(int i=2; i<k/2; i++)
{
if(k%i == 0)
return FALSE;
}
return TRUE;
}
main()
{
int a = 16, b = 100;
int i = a;
for(i=a; i<=b; i++)
{
if(isPrimNumber(i))
printf("%d\n\r", i);
}
}
This may be optimized by loop over k=2 to sqrt(k) instead of k/2. It's just a naive way to use sieve method. But no additional space required.
# include<stdio.h>
# include<conio.h>
# include<math.h>
int sieve(int factor,int c[],int size,int a)
{
//i need to chop out all factors of i in the array
//-1 for the number whose factor doesn't exist uptil and 1 for a non-prime number
int i;
if(a==1)
i=1;
for(i=0;i<size;i++)
{
if(c[i]==-1&&(a+i)!=factor&&!((i+a)%factor))
c[i]=1;
}//end of for loop
return 0;
}//end of sieve function
int print(int a ,int b)
{
int size=b-a+1,c[size],i;
for(i=0;i<size;i++)
c[i]=-1;
if(a==1)
c[0]=1;//coz one is not a prime number
for(i=2;i<=(int)sqrt(b);i++)
{
sieve(i,c,size,a);
}//end of for loop
for(i=0;i<size;i++)
{
if(c[i]==-1)
printf("%d\n",i+a);
}
return 0;
}//end of function
int main()
{
int a,b;
printf("this program is made by considering that we have to include a and b as well\n");
printf("enter the lower bound");
scanf("%d",&a);
printf("enter the upper bound");
scanf("%d",&b);
print(a,b);
printf("returned from the function");
getch();
return 0;
}//end of main function
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class PrimeNumbersInRange {
public void primeCheck(int a)
{
//System.out.println("check"+a);
for(int i = 2; i<=a; i++)
{
//System.out.println(a%2);
if(a != i)
{
if( a % i == 0)
{
break;
}
}
else
{
System.out.println(a);
}
}
}
public static void main(String[] args) {
PrimeNumbersInRange prn = new PrimeNumbersInRange();
System.out.println("Please enter the range of numbers");
try
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int init = Integer.parseInt(br.readLine());
int end = Integer.parseInt(br.readLine());
System.out.println("The prime numbers are");
for (;init<end;init++)
{
prn.primeCheck(init);
}
}
catch(Exception e)
{
e.printStackTrace();
}
}
}
import java.util.Scanner;
public class Prime {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int a = s.nextInt();
int b = s.nextInt();
int counter;
System.out.println("Displaying Prime numbers between " + a + " and " + b);
for(int i = a; i <= b; i++) {
counter=0;
for(int j=2;j<i;j++)
{
if(i%j==0)
counter=1;
}
if(counter==0) {
System.out.println(i);
}
}
}
}
static void Main(string[] args)
{
int n = 1, m = 1000000;
if (n % 2 != 0) n++;
for (int i = n + 1; i < m; i = i + 2)
if (IsPrime(i))
Console.WriteLine(i);
}
public static bool IsPrime(int Num)
{
double sqrt = Math.Sqrt(Num);
int N = int.Parse(Math.Ceiling(sqrt).ToString()) + 1;
for (int i = 3; i < N; i = i + 2)
if (Num % i == 0)
return false;
return true;
}
#include<iostream>
using namespace std;
main()
{
int a,b;
cout<<"Enter the Lower limit:";
cin>>a;
cout<<"Enter the Upper Limit:";
cin>>b;
for(int i=a; i<=b; i++)
{
int temp=a;
int temp1=temp/temp;
int temp2=temp % 2;
int temp3=temp % 3;
int temp4= temp % 5;
int temp5=temp % 7;
if(temp1==1 )
{
if(temp2 !=0)
{
if(temp3 !=0)
{
if(temp4!=0)
{
if(temp5!=0)
{
cout<<temp<<"is prime"<<endl;
}
}
}
}
a++;
}
}
return 0;
}
def isPrime(n: Int) = (2 until n).forall(d => n % d != 0)
def primesBtween(a: Int, b: Int): Array[Int] = (b-a) match {
case 0 | 1 => Array()
case i: Int if(i > 0) => println(i);(a until b).toArray.filter(isPrime)
case _ => Array()
}
scala> val primes = primesBtween(6,50)
44
primes: Array[Int] = Array(7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
Use sieve method its more effective but requires additional array of size equals to number of elements between between the range..
- c7c7 October 25, 2012