[konstanz]

hello! okay i was suppose to make a program which generates 1000th prime number! its a beginner's level program so i cant use functions or strings or any high level stuff just basic iterations and condition statements! but ive been trying for 3 days now! i have tried about 20 different combinations but nothing happens! the most it does count the loops correctly for 1000th position and count all the odd numbers! it doesn't no matter what i try compute prime numbers! im going to give my latest code here! can some one please tell me what im doing wrong! its really frustrating when you have tackled arrays and cant make a simple prime number code, its driving me crazy! thank you!

state =0
candidate=1
n=1
while (state <10):
    if candidate%2!=0:
        while(n<(candidate**(1/2)+1)):
            count  =0
            if candidate%n==0:
                count+=1
            if count<2==True:
                candidate +=1
                state+=1
            else:
                candidate+=1
print 'iteration count',state
print 'prime number at this position',candidate

[cnampheonix]

I think you guys are making this a helluva lot harder than it is. So much that, your codes made me question if my prime hw was ever that difficult.
But first, I have to ask that this is python right?

I'm also not an expert when it comes to python so feel free to question all my inputs.
In anycase you guys should stop and go back to the beginning. Your trying to find prime numbers. So start there and find out what makes certain numbers prime. Start with what you know and move on from there. Step by step, do some pseudocode if that helps you.
I guess I can start you off. You can choose to ignore 1 since 1 isn't prime. And we know that 2 is prime so we can incorporate that somehow.

The way I did mine was by making a prime function that focuses on analyzing 1 number. Then I would ask the user what number or how many numbers, range of numbers etc. And call the function from there.

Hope that helps

[macosxnerd101]

While I don't really have any Perl or Python experience, I've got a couple of ideas you may find useful. First- take a look at the Sieve of Eratosthenes for your prime number generation for numbers 2-n. From there, I adopted this algorithm to generate the first n primes using a back-tracking method. That is, keep generating x primes until you exceed the threshold, then backtrack and remove the excess primes.

I've got a Java snippet to do this here: http://www.dreaminco...snippet4601.htm
Same concept, but a different language.

[baavgai]

Neither block of code seems close enough to work from...

Make a function called isPrime that simply returns true or false. If you write it correctly, then the following code will work.

def nthPrime(n):
	count = 0
	value = 1
	while count<n: # repeat until we get up to n
		value += 1 # we start at 2
		if isPrime(value):
			count += 1
	return value

Hope this helps.

[konstanz]

Anonymous, on 10 June 2010 - 03:41 PM, said:

import math
testnum = 3
maxprime = input("nth prime number:")
if maxprime >= 1:
print 2
primecount = 1
while primecount < maxprime:
for num in range(2,int(math.sqrt(testnum)+2)):
if testnum%num ==0:
break
if num == int(math.sqrt(testnum)+1):
print testnum
primecount = primecount + 1
testnum = testnum + 2





I did it like this, and it looks similar to yours, and I think mine works. However, it would be nice if somebody could tell me how to clean it up some more but still use the same method.

hey man this doesnt run above n=10

[cnampheonix]

There are alot of issues in the code given by the guest. What's happening is that because of the small limited range in the for loop. The "primecount" never goes up high enough to stop the while loop. So the program never ends after the user has inputed a "nth prime" 5 or higher. This wouldn't even find prime numbers if you fixed the range. It would just keep printing odd numbers.

I see that you tried to use a method of finding multiples between 2 and sqrt(n).
But like I said before your making things way to complicated and confusing. The way baavgai explained before is probably the easiest and simplest way to solve finding primes.

Quote

Make a function called isPrime that simply returns true or false. If you write it correctly, then the following code will work.

def nthPrime(n):
        count = 0
        value = 1
        while count<n: # repeat until we get up to n
                value += 1 # we start at 2
                if isPrime(value):
                        count += 1
        return value

Primes are numbers divisible by 1 and itself. In other words, if a number is divisible by anything besides 1 and itself, it wouldn't be prime. But trying to find if a number is divisible by 2, 3, 4, 5 ,6 etc... would be annoying wouldn't it? Maybe theres a simpler way to know?

[konstanz]

cnampheonix, on 12 June 2010 - 10:33 AM, said:

There are alot of issues in the code given by the guest. What's happening is that because of the small limited range in the for loop. The "primecount" never goes up high enough to stop the while loop. So the program never ends after the user has inputed a "nth prime" 5 or higher. This wouldn't even find prime numbers if you fixed the range. It would just keep printing odd numbers.

I see that you tried to use a method of finding multiples between 2 and sqrt(n).
But like I said before your making things way to complicated and confusing. The way baavgai explained before is probably the easiest and simplest way to solve finding primes.

Quote

Make a function called isPrime that simply returns true or false. If you write it correctly, then the following code will work.

def nthPrime(n):
        count = 0
        value = 1
        while count<n: # repeat until we get up to n
                value += 1 # we start at 2
                if isPrime(value):
                        count += 1
        return value

Primes are numbers divisible by 1 and itself. In other words, if a number is divisible by anything besides 1 and itself, it wouldn't be prime. But trying to find if a number is divisible by 2, 3, 4, 5 ,6 etc... would be annoying wouldn't it? Maybe theres a simpler way to know?

but thats the problem. i apparently cant calculate primes! my 'prime number check' doesnt work like its supose to! actually it just checks for the odd numbers which is very odd! i kind of tries to exclude all the even numbers as they are not primes! n then tried that 3 to sqrt(n) range check method! its cuts the checking to less than half other then that i cant think of anyother way of checking

ramu, on 14 June 2010 - 01:20 AM, said:

ramu, on 14 June 2010 - 01:11 AM, said:

konstanz, on 04 June 2010 - 05:02 AM, said:

hello! okay i was suppose to make a program which generates 1000th prime number! its a beginner's level program so i cant use functions or strings or any high level stuff just basic iterations and condition statements! but ive been trying for 3 days now! i have tried about 20 different combinations but nothing happens! the most it does count the loops correctly for 1000th position and count all the odd numbers! it doesn't no matter what i try compute prime numbers! im going to give my latest code here! can some one please tell me what im doing wrong! its really frustrating when you have tackled arrays and cant make a simple prime number code, its driving me crazy! thank you!

state =0
candidate=1
n=1
while (state <10):
    if candidate%2!=0:
        while(n<(candidate**(1/2)+1)):
            count  =0
            if candidate%n==0:
                count+=1
            if count<2==True:
                candidate +=1
                state+=1
            else:
                candidate+=1
print 'iteration count',state
print 'prime number at this position',candidate

ummmm is this suppose to mean anything?

[cnampheonix]

Looks like we won't get anywhere so Ill give you a little push to see if that helps jump anything. Like I've stated before we need to start at the beginning with what we know and move on from there. So what were trying to do is in essence find out if a number is prime or not. Don't try to make a function that would find a range of numbers that are prime because then you would be incorporating too many steps at once making things more complex. Simplicity and step by step is the key.

We'll use the process baavgai pointed out earlier.

We start off with working on finding if a number is prime. We know that the number 1 cannot be prime so in our isPrime(value): we will first state that conditional:

if value == 1: 
    return False

Next we know that number 2 is prime and being that it is a even number can account for all other even numbers:

if value == 2:
    return True
if value % 2 == 0:
    return False

This will check for all other even numbers and return that they are not primes.

To check for all other numbers
we'll use an "else" so all other numbers are funneled here. And we should probably start with 3 since we already checked for 1 and 2. So starting with 3 we'll see if the number given lets say for example number 11 is prime. Well we could first start off with checking if the number % 3 == 0. That would allow us to know if there are any numbers divisible by 3. And if there are then we can say False. But what about all the other numbers in between 3 and 11. We could increment 3 and keep modding so we know that no number between 3 and 11 is divisible by 11. After finding that all checks did not return False. Then we can finally say that 11 is True and thus Prime.

Knowing this we would need:
To initialize 3.
Probably have a while loop.
also increment the variable with 3
Out of the while loop have a return True.


This is just the way I did mine for isPrime. After your able to get the function you can mess around and call it in another function and print, or do what baavgai did. Whatever you like. Hope this helps

This post has been edited by cnampheonix: 14 June 2010 - 09:55 AM

[RussianScience]

I did the same assignment today (I'm guessing you are taking the MIT open courseware class?) and this is what I came up with, hope it helps.

number = input('enter prime you wish to find')
x = 5
y = 3
while (y<(number+1)):
    if ((x/2)*2)<x:
        z = x-1
        while(x%z>0):
            z = z-1
        if z == 1:
            y = y+1
            x = x+1
        else: x = x+1
    else: x = x+1
x = x-1
print x

It's slightly different from the one you need in that you input any number (n) and it gives you the nth prime, but it can be changed to only find the 1000th prime with a few small modifications.

This post has been edited by RussianScience: 07 May 2011 - 01:50 PM

[handihans]

try this:

for n in range(4, 20):
    for x in range(2, n):
        if n % x == 0:
            break
    else:
        # loop fell through without finding a factor
        print n, 'is a prime number'

you can change the range if you want more or less primes
hope it helps!

This post has been edited by atraub: 13 July 2011 - 07:29 PM
Reason for edit:: added code tags

[Sterkte]

Here is what I did to make sure the primes were not divisible by other primes. It is a bit sloppy still, but gets the job done. I am not good enough to shorten up things so everything is probably as inefficient as can be.
It seems most people miss failing primes after the 10th or 20th due to not checking for % of 3, 7, 11 etc...
Also, not sure how to make the code appear indented here, you will have to figure out indents.

#ensure number entered is int and > 1(this is copied from someone elses code to ensure number is int, sorry cannot #remember who it was though)
isnum = False
while isnum == False:    
    tarnum = raw_input('Enter which nth prime you would like to find: ')
    try :
        tarnum = int(tarnum)
        if tarnum < 1:
            isnum = False
            print 'You entered a negative number, please enter which prime to calculate'
        else:
            isnum = True
    except:
        isnum = False
        print 'This is not a number, please enter which prime to calculate'
#Set up variables
lisprime = [2]
testpass = True        
curprime = 3    
listindex = 1
testindex = 1
rootprime = 0    
lisprime.append(curprime)
#loop to get nth prime
while listindex <= tarnum:
    rootprime = curprime**0.5
#check if divisible by any primes less than the root
    while lisprime[testindex]<=rootprime:
        if curprime%lisprime[testindex] > 0:
            testindex += 1
            testpass = True
        else:
            testpass = False
            break
#If it is a prime, add it to lisprime
    if testpass == True:
        lisprime[listindex]=curprime
        lisprime.append(curprime)
        listindex += 1
#only test odd numbers(inc by 2)
    curprime += 2
    testindex = 1
print 'This is the requested prime number:', lisprime[listindex-2]

This post has been edited by macosxnerd101: 13 July 2011 - 06:15 AM
Reason for edit:: Fixed code tags

[Giggety-Giggety]

I just did this for MIT OCW. here's how I did it.

 def prime(x):
    if x == 1:
        return 0
    else:
        limit = x/2
        div = 2
        check = 0
        while div <= limit:
            if x % div == 0:
                check = 1
            div = div +  1
        if check == 0:
            return 1
        else: return 0

num = 1
count = 0
while count < 999:
    if prime(num) == 1:
        count = count + 1
    num = num + 2
num = num - 2
print(num)