Question

Anyways, easier way for prime numbers were developed by mathematicians, namely Fermat's primality test:

if ((2**dividend)-2)%dividend==0: prime += [dividend,] then number is prime This prime check worked, which meant I only needed to control the flow until my prime list was created. I was able to generate the prime list, and my code is very short and simple. SO MUCH EASIER! Is this cheating?

Answer 1

ok the issue is not is it simple, it is can you think like a programer? flow control. this is the first assignment in a introduction course, people aren't given tuples, or lists, or anything mutable for that matter, or know the concept of iteration. assume that people are given the following ideas:
assignment (=)
while loop
comparators (==,>,<)
modulus (%)
basic math operations(+,-,/,*)
if
elif
else
i might be missing one but that is all you need to make your first neat program, yes there are better ways to do this program, i've had to revamp my prime code for project euler, it asked for the 148934th prime(your asked for something else, but that happens to be the prime you come up with), and my code crunched that in less then time then my ps1a code did the 3000th prime (keep in mind the ps1 code gets slower as it goes farther, at least if you do the assignment like it was meant to be done)
if you can do it better, good for you, just google python prime code and I'm sure you'll get at least a half dozen pieces that are amazingly fast and simple.

later on in the course the prof does teach you to go online and find better answers by smarter people, and how to do so. that is not the point now, right now its just find your primes with the simple concepts you have been taught, we'll hit more complex ideas later, we'll build to them and it'll be easier to understand. this is just the beginning and it gets much easier

also you want it to run
prime.append(dividend), adding a single item to a list like that is just tacky

Answer 2

or un-pythonic even

Answer 3

so , i don't see how it could be faster - from what i just read (thnx for that by the way):

you still have to do the test for all dividends in the range (2 to candidate) to Ensure it is prime.

if you only use a subset in the range (2 to candidate) you can only say that it is Probably prime.

also - (div ** (candidate-1) % candidate) != 1 - seems like there are more calcs going on than - candidate % div == 0

it is the same algorithm, just a different test - yes?
http://dpaste.com/578620/

Answer 4

"candidate mod div" test with same result
http://dpaste.com/578629/

Answer 5

the method is simple, but computationally for larges numbers (n) does not apply (2**n). It is best to use iterations, conditionals.

Answer 6

well if you go under the theory that any non prime has to have factors that are in turn prime you can make a piece of code like this
also happens to to be my answer code to project Euler problem 10
http://dpaste.com/578916/
this gives me a testing range of all primes between 2-math.sqrt(potencial_prime), this makes a giant difference, hell if you drop the square root bit then it runs 10 slower, maybe even more

Answer 7

yep, i came across a few things that said you only have to test divisors up to sqrt(candidate) with the candidate mod divisor test.