Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
Alban18
Group Title
Man I'm pulling my hair out to solve this simple code. Can someone please help me.
Write a program that computes and prints the 1000th prime number. (I'm doing this in Java btw.)
This is beginning comp sci course so they I'm sticking with selection and repetitions structures. Nothing fancier than introductory comp sci code.
 one year ago
 one year ago
Alban18 Group Title
Man I'm pulling my hair out to solve this simple code. Can someone please help me. Write a program that computes and prints the 1000th prime number. (I'm doing this in Java btw.) This is beginning comp sci course so they I'm sticking with selection and repetitions structures. Nothing fancier than introductory comp sci code.
 one year ago
 one year ago

This Question is Open

drichmond6021023 Group TitleBest ResponseYou've already chosen the best response.0
I have a solution to this that'a a little bit clunky. This is Python, I think I have basically the same inelegant solution for Java somewhere. Let me know if you come up with something that doesn't have to start counting at three. import math countPrime=1 testNumber=3 print '2 is prime' print '3 is prime' while countPrime < 999: testNumber=testNumber+1 divisor= int(math.sqrt(testNumber)) divisorCount=0 while divisor > 1: if (testNumber%divisor==0): divisorCount=divisorCount+1 divisor=divisor1 if (divisorCount==0): print str(testNumber) +'is really prime' + str(countPrime) countPrime=countPrime+1 print 'end'
 one year ago

Gianko15 Group TitleBest ResponseYou've already chosen the best response.1
I've got a code with yield and next, it creates a list of the n first prime numbers, hope it hepls, python btw: def firstNPrimes(n): # n = how many primr numbers you want priL = [] aux = 0 i = 2 while len(priL) < n: if i == 2 or i == 3: priL.append(i) else: for j in priL: if i%j == 0: aux = 1 if aux == 0: priL.append(i) i += 1 aux = 0 return priL
 one year ago

TuringTest Group TitleBest ResponseYou've already chosen the best response.1
just for posterity, I wrote one right now in python that does not use a function definition, and only gives the 1000th prime (sorry, nobody here seems to use JavaScript) primes = [] testPrime = 2 while len(primes) < 1000: isPrime = True for prime in primes: if testPrime%prime == 0: isPrime = False testPrime += 1 if isPrime == True: primes.append(testPrime) print primes.pop()
 one year ago

Gianko15 Group TitleBest ResponseYou've already chosen the best response.1
I forgot not to include definition xD!
 one year ago

KonradZuse Group TitleBest ResponseYou've already chosen the best response.0
Now what do you mean by the 1000th prime #? Do you mean the actual # that is the 1000th(whatever that may be) or do you mean a number that you enter? Please be specific.
 one year ago

Gianko15 Group TitleBest ResponseYou've already chosen the best response.1
Turing's gives the first 1000 primes, mine give you the # you want (n).
 one year ago

KonradZuse Group TitleBest ResponseYou've already chosen the best response.0
Idk why schools give such useless assignments such at this, they are NEVER used in the real world; however from what I'm posting it will help you think mathematically and help you with problem solving. Trivial Cases We learned numbers are prime if the only divisors they have are 1 and itself. Trivially, we can check every integer from 1 to itself (exclusive) and test whether it divides evenly. For example, one might be tempted to run this algorithm: //checks whether an int is prime or not. boolean isPrime(int n) { for(int i=2;i<n;i++) { if(n%i==0) return false; } return true; } This doesn’t seem bad at first, but we can make it faster – much faster. Consider that if 2 divides some integer n, then (n/2) divides n as well. This tells us we don’t have to try out all integers from 2 to n. Now we can modify our algorithm: //checks whether an int is prime or not. boolean isPrime(int n) { for(int i=2;2*i<n;i++) { if(n%i==0) return false; } return true; } With some more efficient coding, we notice that you really only have to go up to the square root of n, because if you list out all of the factors of a number, the square root will always be in the middle (if it happens to not be an integer, we’re still ok, we just might overapproximate, but our code will still work). Finally, we know 2 is the “oddest” prime – it happens to be the only even prime number. Because of this, we need only check 2 separately, then traverse odd numbers up to the square root of n. In the end, our code will resemble this: //checks whether an int is prime or not. boolean isPrime(int n) { //check if n is a multiple of 2 if (n%2==0) return false; //if not, then just check the odds for(int i=3;i*i<=n;i+=2) { if(n%i==0) return false; } return true; } As you can see, we’ve gone from checking every integer (up to n to find out that a number is prime) to just checking half of the integers up to the square root (the odd ones, really). This is a huge improvement, especially considering when numbers are large. Repetitions Let’s say you write a program where you’re asked to check whether many numbers are prime; not just once. Even though our program above is highly optimized for that algorithm, there exists another way specifically suited for this situation: The Prime Sieve. Here’s the basic idea: Assume every integer greater than or equal to 2 is prime. Start at the beginning of the list, if the number is prime, cross out every multiple of that number off the list. They are not prime. Go to the next number, if it is crossed out, skip it – it is not prime. If it is not crossed out, it must be prime, cross out it’s multiples. Repeat Let’s see what this means. Consider the list: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... 2 is prime… cross out it’s multiples. Our list now looks like: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 … You can see why 2 is the only prime. By now doing it with 3, we cross out 6 (already crossed out), 9, 12(already crossed out), 15, etc. Eventually, your list will look like this: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 … And our primes are the ones left over: (2,3,5,7,11,13,17,19,23,29,…). In code, you might want to keep track of this list as an array. Meaning you’ll go through n numbers to set up this “sieve”, but you’ll make up for it when repeatedly calling the function, since it will return an instantaneous value whether a number is prime or not. Here’s what it will look like. Of course, you can edit this yourself to suit your needs: import java.util.Arrays; //global array just to keep track of it in this example, //but you can easily do this within another function. // will contain true or false values for the first 10,000 integers boolean[] primes=new boolean[10000]; //set up the primesieve public void fillSieve() { Arrays.fill(primes,true); // assume all integers are prime. primes[0]=primes[1]=false; // we know 0 and 1 are not prime. for (int i=2;i<primes.length;i++) { //if the number is prime, //then go through all its multiples and make their values false. if(primes[i]) { for (int j=2;i*j<primes.length;j++) { primes[i*j]=false; } } } } public boolean isPrime(int n) { return primes[n]; //simple, huh? }
 one year ago

Gianko15 Group TitleBest ResponseYou've already chosen the best response.1
Well that's a big argument this is how my face look like now :P .... dw:1353791266808:dw
 one year ago

KonradZuse Group TitleBest ResponseYou've already chosen the best response.0
Not at all, what they teach yo in school is mostly useless.
 one year ago

KonradZuse Group TitleBest ResponseYou've already chosen the best response.0
dw:1353793840818:dw
 one year ago

Alban18 Group TitleBest ResponseYou've already chosen the best response.0
Thank guys, I really appreciate the help. Sorry I didn't acknowledge anybodies comments when when I initially made this.
 one year ago
See more questions >>>
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.