Interview Question
Country: United States
#include<bits/stdc++.h>
#define elif else if
#include<assert.h>
using namespace std;
#define limit 100000001
vector<bool>isprime(limit,true);
unsigned int a[5761455];
void sieve()
{
isprime[0]=isprime[1]=false;
int s=sqrt((double)limit);
for(unsigned int i=2;i<=s;i++)
{
if(isprime[i])
for(unsigned int j=i;i*j<=limit;j++)
isprime[i*j]=false;
}
int cnt=1;
a[0]=2;
for(int i=3;i<=limit;i+=2)
if(isprime[i])
a[cnt++]=i;
}
int main()
{
//std::ios::sync_with_stdio(false);
int t;
cin >> t;
sieve();
while(t--)
{
int n;
cin >> n;
cout << a[n-1] << endl;
}
return 0;
}
One of the easiest yet efficient methods to generate a list of prime numbers if the Sieve of Eratosthenes.
Here’s the basic idea:
>Create a list with all positive integers (starting from 2 as 1 is not considered prime).
>Start at the first valid number (at this point all are valid) and eliminate all its multiples from the list. So start with 2, and eliminate 4, 6, 8, 10, 12 and so on.
>Once all the multiples are eliminated advance to the next valid number (one that has not been eliminated) and repeat the process, until there are no more valid numbers to advance to.
Sieve of Eratosthenese algo
public class PrimeSieve {
public static void main(String[] args) {
final int N = 500000;
// initially assume all integers are prime
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {
// if i is prime, then mark multiples of i as nonprime
// suffices to consider mutiples i, i+1, ..., N/i
if (isPrime[i]) {
for (int j = i; i*j <= N; j++) {
isPrime[i*j] = false;
}
}
}
// count primes
int kPrime = Integer.parseInt(args[0]);
// for N=500000 we can only have 41538 primes
if ( kPrime <= 0 || kPrime > 41538 ) {
System.out.println("Invalid Input.Please try again!!!");
return ;
}
int i = 2;
for (int primes = 0; primes < kPrime; i++) {
if (isPrime[i]) primes++;
}
System.out.println("The " + kPrime + "th number of prime = " + (i-1) );
}
}
Output:
$ java PrimeSieve 234
The 234th number of prime = 1481
$ java PrimeSieve 0
Invalid Input.Please try again!!!
static int arr[500000]={0};
arr[1]=1;
for (i = 2; i < 500000; i++)
{
for (j = i * i; j < 500000; j+=i)
{
arr[j] = 1;
}
}
I hope this helps, algorithm used is sieve of Eratosthenes; use just have to apply your particular condition now
you can do it using Sieve of Eratosthenes algorithm which runs in O(nlogn)
- vinod1054 October 23, 2015