NVIDIA Interview Question
Software Engineer / DevelopersHmm, still how would you use the Sieve of Eratosthenes to elegantly find the n'th prime? Say, n=178, how do you till what upperbound to perform the sieve on? Would it be 1000, 10000, etc.? We can always be conservative and keep growing the upper bound and re-sieve for the grown set, but that doesn't seem elegant.
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <time.h>
int main(){
int i;
printf("Find primes up to: ");
scanf("%i",&i);
clock_t start, stop;
double t = 0.0;
assert((start = clock())!=-1);
//create prime list
int prime[i];
int c1, c2, c3;
//fill list with 0 - prime
for(c1 = 2; c1 <= i; c1++){
prime[c1] = 0;
}
//set 0 and 1 as not prime
prime[0]=1;
prime[1]=1;
//find primes then eliminate their multiples (0 = prime, 1 = composite)
for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){
if(prime[c2] == 0){
c1=c2;
for(c3 = 2*c1;c3 <= i+1; c3 = c3+c1){
prime[c3] = 1;
}
}
}
stop = clock();
t = (double) (stop-start)/CLOCKS_PER_SEC;
//print primes
for(c1 = 0; c1 < i+1; c1++){
if(prime[c1] == 0) printf("%i\n",c1);
}
printf("Run time: %f\n", t); //print time to find primes
return 0;
}
A New Formula for Generating Primes
Some simple expressions can generate a surprisingly large number of primes, whole numbers that are evenly divisible only by themselves and 1. The remarkable formula x2 + x + 41, for example, yields an unbroken string of 40 primes, starting at x = 0.
Another simple, prime-rich formula, x2 + x + 17, generates prime numbers for all integer values of x from 0 through 15. Searching for a polynomial formula that produces all primes, however, would be fruitless. Mathematicians proved years ago that no polynomial expression with integer coefficients has only prime values.
But there are other possibilities. So people have continued to look for simple prime-generating functions, and Rutgers graduate student Eric Rowland has just found a new one. In a paper published in the Journal of Integer Sequences, Rowland defines his formula and proves that it generates only 1s and primes.
Here's Rowland's recursive formula for generating primes.
Define a(1) = 7.
For n greater than or equal to 2, set a(n) = a(n – 1) + gcd(n, a(n – 1)). Here "gcd" means the greatest common divisor.
For example, given that a(1) = 7, a(2) = a(1) + gcd(2, 7) = 7 + 1 = 8.
The prime generator is then a(n) – a(n – 1). The resulting numbers are the so-called first differences of the original sequence.
Here are the first 23 values of the a sequence:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69
Here are the first differences of these values:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23
Ignoring the 1s, we find that Rowland's formula generates the primes 5, 3, 11, 3 (again), and 23. If we continue the process and remove duplicates, the formula generates the prime sequence 5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, . . .
Rowland describes his formula in the "A New Kind of Science" blog. He notes that the formula originated in 2003 at the NKS summer school, where participants discover and explore computational systems that exhibit "interesting" behavior.
"This was a surprising discovery, since previously there was no known reliable prime-generating formula that wasn't expressly engineered for this purpose," Rowland said. Rowland went on to prove mathematically that this recurrence produces only 1s and primes. He has created a Mathematica demonstration for exploring the recurrence.
Rowland's formula is unlikely to lead to more efficient ways of generating large primes, a crucial operation in cryptography. His formula produces the prime p only after first generating (p – 3)/2 1s. "So it takes a really long time to generate a large prime," Shallit said. Rowland "has a method for skipping over those useless 1s, but doing so essentially requires an independent test for primality."
Are there other formula's like Rowland's? Recently, French mathematician Benoit Cloitre proved that by setting b(1) = 1 and b(n) = b(n – 1) + lcm(n, b(n – 1)) for n greater than or equal to 2, b(n)/b(n – 1) – 1 is either 1 or prime.
finding 15th prime number
public class PrimeNumbe {
/**
* @param args
*/
public static void main(String[] args) {
int i=0,mod=0,count=1;
for (i=2;count<=15;i++){
mod=i-1;
while(i%mod!=0&&mod>1){
mod--;
}
if(mod==1)
{
System.out.println("testing "+i);
count++;
}
}
System.out.println("Prime Number:: "+(i-1));
}
}
You'll have to change to what ever method you use to input or output a value. I'm using IO.java.
Other than that, works like a charm.
public class NthPrime
{
public static void main(String[]args)
{
int count=0;
int numTest=1;
int finalPrime=0;
System.out.println("Enter a value 'N' to find the 'Nth' prime number.");
int primeN = IO.readInt();
if(primeN == 0)
{
IO.reportBadInput();
return;
}
do
{
double limit = Math.sqrt(numTest);
boolean prime = true;
if(numTest==1)
{
prime = false;
}
else if(limit<2)
{
prime=true;
}
else
{
for(int divisor = 2; divisor <= limit && prime; divisor++)
{
if(numTest % divisor == 0)
{
prime = false;
break;
}
/*
else
{
prime=true;
finalPrime = numTest;
}
*/
}
}
if(prime==true)
{
count=count+1;
finalPrime=numTest;
numTest++;
System.out.println("The current prime number stored is: " + finalPrime);
}
else
{
numTest++;
}
}while(count<primeN);
IO.outputIntAnswer(finalPrime);
}
}
A little C code for this
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define PRIME 2
int main(int argc, char * argv[]) {
int n=3; //start from this number
int i,j,flag;
if(argc != 2) {
fprintf(stderr,"usage: ./prime_no <nth>.\n");
exit(-1);
}
int count = atoi(argv[1]);
int primes[count];
primes[0] = PRIME;
i = 0;
while(i<count) {
flag = 0;
for(j=0; j<=i; j++) {
if(n % primes[j] == 0) {
flag = 1;
break;
}
}
if(flag == 0) {
i++;
primes[i] = n;
}
n++;
}
for(i=0;i<count;i++) {
printf("%d ", primes[i]);
}
printf("\n");
return 0;
}
In complexity of O(n) to O(n*m), n is largest number checked, and m is recorded prime no so far.
sample output:
$ ./prime_no 20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
$ ./prime_no 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
$ ./prime_no 101
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547
$ ./prime_no 103
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563
#include<stdio.h>
#include<math.h>
main(){
int n;
scanf("%d",&n);
int i,mod,count=1;
for(i=2;count<=n;i++){
mod=sqrt(i);
while(i%mod!=0 && mod>1){
mod--;
}
if(mod==1){
count++;
}
}
printf("%d \n",i-1);
}
#include<stdio.h>
void main()
{
int N;
int i=0;
int k=2;
int j;
printf("how many prime number to print ?");
scanf("%d",&N);
while(i<N)
{
for(j=2;j<k/2;j++)
if(k%j==0)
break;
if(k%j!=0 || k==j)
{
printf("\t %d",k);
i++;
}
k++;
}
getch();
}
o/p
how many prime number to print ?103
2 3 5 7 11 13 17 19 23
29 31 37 41 43 47 53 59 61 67
71 73 79 83 89 97 101 103 107 109
113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199 211 223 227
229 233 239 241 251 257 263 269 271 277
281 283 293 307 311 313 317 331 337 347
349 353 359 367 373 379 383 389 397 401
409 419 421 431 433 439 443 449 457 461
463 467 479 487 491 499 503 509 521 523
541 547 557 563
simple program to print nth prime no
#include <stdio.h>
int main()
{
int count=1;
int a = 2;
int n;
printf("enter position\n");
scanf("%d",&n)
while(count<=n)
{
int b = 2;
int prime = 1;
while(b*b<=a)
{
if(a%b==0)
{
prime=0;
break;
}
b++;
}
if(prime)
count++;
a++;
}
a--;
printf("The %d th prime no will be: %d",n,a);
return 0;
}
public class NthPrimeNum {
public static void main(String[] args) {
int n = 46;
int count = 3;
if (n == 3) {
System.out.println(5);
} else {
int nthNum;
for (nthNum = 7; count < n; nthNum = nthNum + 2) {
if (isPrime(nthNum)) {
count++;
}
}
System.out.println(nthNum - 2);
}
}
public static boolean isPrime(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
public class NthPrimeNum {
public static void main(String[] args) {
int n = 46;
int count = 3;
if (n == 3) {
System.out.println(5);
} else {
int nthNum;
for (nthNum = 7; count < n; nthNum = nthNum + 2) {
if (isPrime(nthNum)) {
count++;
}
}
System.out.println(nthNum - 2);
}
}
public static boolean isPrime(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
Every prime no is of the form 6k+1 or 6k-1 except the initial cases i.e. 2 and 3 which has to be taken care of.
I guess that is just an extension of saying that every prime no. is 2k+1 (except 2). Or that every prime no. is either 3k+1 or 3k+2 (except 3). Doesn't really help solve this problem.
a 6k
b 6k+1
c 6k+2
d 6k+3
e 6k+4
f 6k+5 = 6k-1
6k = 2*3k cannot be prime
6k+1 possible prime
6k+2 = 2(3k+1) cannot be prime
6k+3 = 3(2k+1) cannot be prime
6k+4 = 2(3k+2) cannot be prime
6k-1 possible prime
The same theory to 3k+1, 3k+2, but it gives you a larger step and we can ignore more numbers
@ raj
- googler August 25, 2009True!!!