NVIDIA Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

@ raj
True!!!

- googler August 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why is every prime no of the form 6k+1 or 6k-1

- gaurav August 25, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is because every third number is divisible by 3 and every second number is divisible by 2. Suppose a number, say 17, than
15 16 17 18 19 ............... now u see number below and above it are divisible by 2, and either of it has to be a multiple of 3, so this formula holds !

- mastermind9990 August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

while every prime number will satisfy 6k+1 or 6k-1 ,other non prime numbers might also satisfy the condition. for example 25 can be represented as 6(4)+1.

How can this condition be used to find n the prime number?

- hopebasedcoder August 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Read on the Sieve of Eratosthenes

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

- Anonymous August 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

great thanks i love wiki sol

- cunomad August 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sieve of Eratoshenses may be the least preferable way.
There are better alternatives.

- Siva August 30, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

then why don't you list them? your comment adds no value to this thread.

- Anonymous March 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sieve of Eratosthenes is the standard way of solving this problem!

- LLOLer August 26, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hmm, 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.

- Mohit August 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- manoj August 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

prime being 6k-1 or 6k+1 is very good. using erastones we are touching upon every number in Sieve of Eratosthenes algo whereas here that is reduced...

- shashi August 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys...the Question says to find the nth prime number not all the prime numbers till n

- Anonymous March 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- sumit saxena March 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
		
		
	}

}

- PM June 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- Kevin N. February 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Jie March 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

- Anonymous December 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#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

- govind.chauhan143 June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- sudip March 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- Anonymous April 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- Anonymous April 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- raj August 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Mohit August 27, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- maillist.danielyin September 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

put k=4, 6k+1= 25 but 25 is not a prime number

- malikchandan62 October 22, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More