Question

ok there is my question:
i did the 1000th prime problem but it gives me wrong resultats....
fact is i did it with lecture 2 info as i thought that it was there it belonged, so i would like to resolve it still with lecture 2 info (max while loop) for now.

i would like smone to help me find the mistakes but i would like to keep searching the solution myself so no spoilers:P xD

so here is my code:
http://pastebin.com/sNFfuM9C

ty you all for your time and effort in advance:)

Answer 1

hmm, I haven't really used python so it is a bit hard to read, but what result do you get and what should you get?

Answer 2

at start i got a line of 1111111111...and thats not right^^
the program has to calculate the 1000th prime number

Answer 3

changing tprm (thousandprimenumber) into a str now it gives me 1 as result.....

Answer 4

the 1000th prime problem is to find the 1000th prime number? or the first 1000th prime numbers? you have to be clear if you want help..

Answer 5

ok i got it.. first of all use the appropriate data structure..

Answer 6

if u mean for loops i know i should use that but i beleiev it can be done without aswell(since as i stated i thought it was a lecture 1 assignment)

Answer 7

data structure is NOT a for loop :)

Answer 8

you need to store the data somehow.. that's why you need a data structure

Answer 9

arrays?

Answer 10

hm.. you could use arrays as well...

Answer 11

correct me if i'm wrong but doesn't that code think that every number is a prime number?
I can't se where you handle the case of a number not being prime

Answer 12

fact is i dont need it to remember all the primes till the 1000th...i just need it to count everytime it finds one and print out the 1000th

Answer 13

hmmm invidos give me a min for that

Answer 14

if you want to be fast you have to use data structures...

Answer 15

you can't do citation without an array or something similar..

Answer 16

while(prmcnd%cctrl!=0 and cctrl<prmcnd/2):
cctrl=cctrl+1
this is the part where i check if its a prime
basicaly it says while primecandidate%control candidate is not 0 and the cctrl 's limit is half or the prmcnd ill +1 the counter so i check if it can be divided to next one...

Answer 17

you don't need to ceck up to n/2 to see if n is prime.. up to sqrt(n) is good... but citation is even better...

Answer 18

im sry what is citation?

Answer 19

citation is a proccess in which you can find prime numbers really fast and using the least memory possible..

Answer 20

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

Answer 21

ok mate i understand what you r trying to say but since my programming lvl atm is low as a while loop:P id like to resolve the problem with that knowledge ...atm how much memory it takes and its speed is not that important to me...

Answer 22

should oddint be inside the while loop?

Answer 23

line 10...

Answer 24

ok then you can use the bruteforc'y' method and check the divisors of each number you encounter..

Answer 25

I don't think that oddint can ever be higher than 2 with that code

Answer 26

hmm im gonna check it now then ty both for those hints...will come back if i have news:P

Answer 27

so ye it thinks that every odd number is prime.....and ther eis my prob i dont know how to cotrol that ...but ill keep sqeezing my brain till i get a solution xD ty again both

Answer 28

what is prime number? do you know?

Answer 29

7919

Answer 30

seems legit :P

Answer 31

it is right

Answer 32

right.. http://primes.utm.edu/lists/small/1000.txt

Answer 33

oh hahah read wrong ye i know what is a prime number ...thought u wanted the solution i should get xD

Answer 34

good job.. now you can study citation and make a faster algorithm ;)

Answer 35

well but still i didnt resolve it as i wanted:P will get it ...^^

Answer 36

could you reupload your code?

Answer 37

@MicroBot it gives the right answer.. i suppose it is correct :P

Answer 38

http://pastebin.com/KPzUz9jA
it does not give it i checked the answer from the same table u linked xD

Answer 39

you have to make a procedure that takes one number and tells me if it is a prime or not

Answer 40

btw isnt there a sqrt function?

Answer 41

yeahp..

Answer 42

so which one is it?:P

Answer 43

if you are talking about the sqrt function in python it's the sqrt() ..

Answer 44

so why it sees it as error?:(

Answer 45

while(prmcnd%cctrl!=0 and cctrl< sqrt(prmcnd)):
NameError: name 'sqrt' is not defined

Answer 46

import math?

Answer 47

im not sure what u mean

Answer 48

i am not sure whether or not there is an sqrt function in python.. i can't program in python..

Answer 49

im sry my questions might seem stupid but its the 1st time im doing this

Answer 50

i suppose i need some kind of a library for it

Answer 51

you can ask whatever you want.. stupid questions are justified :)

Answer 52

Python 2.7.1 (r271:86832, Apr 12 2011, 16:15:16)
[GCC 4.6.0 20110331 (Red Hat 4.6.0-2)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from math import sqrt
>>> sqrt(9)
3.0
>>> sqrt(2)
1.4142135623730951
>>>

with some google reasearch i found this.. it seems to be ok

Answer 53

ye it works...python surpises me xD i mean i would never imagine that i can write 'from math import sqrt'...C is so different

Answer 54

i know c as well and i would never learn python :P

Answer 55

anyway.. make the function :P

Answer 56

well i learned some C and C++ but since my programming teacher thought we know already all...i wanted to learn base programming logic and those lessons seems very ineresting plus the prof is very understandable...and then i can rly learn C and other ones:)

Answer 57

good...

Answer 58

import math
is python's version of
#include <math.h>

it just has the option of
from math import *
to bring in an entire module, and use it in the current namespace.
alternatively, you can import individual functions to the current namespace:
from math import sqrt



If you want a quick and dirty method for checking is small numbers are prime, you should use Trial Division.


Trial division is a method where you go through each number smaller than the prime number and check divisibility.

What your code does currently is check for divisibility by 2, and only 2.

This is the simplest way, but probably the least efficient.


Basically:

count = 1
candidate = 2

#you want to iterate over all possible candidates and then stop when you've seen 1000 primes
while count <1000:

#you want to go through all prime candidates
#advanced techniques allow you to skip these (skip all divisible by 2, sometimes more)
candidate+=1

#you need to keep track of whether the current candidate is prime
#this is put here, so we reset it to true before checking each candidate
isprime=True

#go through all possibile divisors
#advanced techniques allow you to skip all non-primes here
#you may also stop at sqrt(candidate) (+1, because of how range() works)
#this is because if there's a factor above the square root, there's always one below it
for i in range(2,candidate):

#check divisibility of each divisor
if candidate%i == 0:
#if it was divisible
#mark that the candidate was not prime
isprime = False
#we stop seeing this as a candidate, as it cannot be prime, so we break
break

# we increment the counter only if it was a prime
if isprime:
count+=1


#we now have 1000 primes we've gone through, so we print the 1000th prime
print (candidate)






A FAR more efficient way is to use a good implementation of a prime sieve, which requires downloading NumPy (scientific computation library):

from numpy import ones, bool, nonzero, r_
def primes(n):
#src: http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a array of primes, 2 <= p < n """
sieve = ones(n//3 + (n%6==2), dtype=bool)
for i in range(1,int(n**0.5/3)+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k//3 ::2*k] = False
sieve[k*(k-2*(i&1)+4)//3::2*k] = False
return r_[2,3,((3*nonzero(sieve)[0][1:]+1)|1)]

This returns all primes below n in a list, but it computes them very fast (for python code).

Answer 59

@bdean20 tyvm! ill see through your suggestions.

Answer 60

if you are trying to find the nth prime, what do you pass to that sieve function to ensure that you will find the nth prime.

i am pretty sure the point of the exercise is to get a feel for flow control and data types not necessarily how efficiently or fast you can find a prime

Answer 61

@bwCA
The number of primes less than n is about 1/log(n), so converting this around:
The number you need to go up to for nth prime is about 10^(1/limit). You should probably give a little bit of a buffer just in case.

If you want to read up on why, there's some good info here:
http://en.wikipedia.org/wiki/Prime_number_theorem

Answer 62

That formula is incorrect, sorry.
The nth prime is about n/(ln(n)-1).

Answer 63

@bdean20 langrage's approximation gives us the numbe of prime numbers below n and it is not accurate...

Answer 64

It's not accurate, but it's a good start.

Above 100, n/ (ln(n)-1) is always greater than the number of primes, which is why it's fine to use the number for setting limits on your prime sieves.

Answer 65

sieves are effective for that small testcases.No need for minor optimizations