Amazon Interview Question
Software Engineer / Developers#include<iostream>
using namespace std;
int main()
{
int n;
cout<<"\nEnter the number:";
cin>>n;
int arr[n+1];
for(int i=1;i<n;i++)arr[i]=i+1;
arr[0]=0;arr[n]=0;
int prime[n];
for(int i=0;i<n;i++)prime[n]=0;
int k;
int p=0;prime[p]=2;
int t=1;
while(arr[1]!=0)
{
k=1;
while(arr[t]!=0)
{
if(arr[t]%prime[p]!=0)
{
arr[k++]=arr[t++];
}
else t++;
}
arr[k]=0;
prime[++p]=arr[1];
t=1;
}
cout<<"\nThe Prime numbers till "<<n<<"are as follows:";
for(int i=0;i<p;i++)cout<<endl<<prime[i];
cin>>k;
return 0;
}
the time complexity of the algo is O(nloglogn) and space complexity is O(n).
still not sure of exact time complexity. any idea??
Use seive of eratosthenes algorithm.
- akshay May 30, 2011O(Nlog(N))