Microsoft Interview Question
Software Engineer in TestsI assume 500 is max number till which we find prime number. this can be modified for more flexibility.
#include <stdio.h>
int main (int argc, char *argv[])
{
int n ;
int i,j,res[500];
n = atoi(argv[1]);
for (i=0;i<=n;i++)
res[i] = -1;
for (i=2;i<=n;i++)
{
if (res[i] == -1)
{
res[i] = 1 ;
for (j=2;(i*j)<=n;j++)
res[i*j] = 0;
}
}
for (i=2;i<=n;i++)
if (res[i] == 1)
printf ("%d ",i);
return 0;
}
1) No need to check even numbers
2) 1 is not a prime
A C# program:
class Program
{
private static ArrayList primeList = new ArrayList();
static void Main(string[] args)
{
getPrime(1); // case 1: 1
getPrime(2); // case 2: 2
getPrime(4); // case 3: 4
getPrime(197); // case 4: a small prime itself
getPrime(9999); ./ case 5: a middle nun-prime
getPrime(65352); // a big one
Console.Read();
}
static void getPrime(int n)
{
if (n < 2)
{
Console.WriteLine(" Number given {0} should greate than 1.", n);
return;
}
primeList.Add(2);
if (n >= 3)
{
primeList.Add(3);
}
int p = 3;
do
{
p += 2;
if (p > n) break;
bool isPrime = true;
for (int i = 1; i < primeList.Count; i++)
{
if (p % (int)primeList[i] == 0)
{
isPrime = false;
break;
}
}
if (isPrime) primeList.Add(p);
} while (p < n);
Console.WriteLine(" Prime numbers less than {0}:", n);
for (int i = 0; i < primeList.Count; i++)
{
Console.Write("{0} ,", (int)primeList[i]);
if (i % 10 == 9)
Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine("---------------------------------");
}
}
void PrintPrime(int n){
- Anonymous October 08, 2009int[n+1] a;
a[0]=a[1]=0;
for(int i=2;i<n+1;i++)
a[i]=1;
for(i=2;i*i<n+1;i++)
if(a[i])
for(int j=i+1;j<n+1;j++)
if(a[j])
if(a[j]%a[i]==0)
a[j]=0;
for(i=0;i<n+1;i++)
{
if(a[i]) printf....
}
}