I made a program to find primes, but it can't find any prime less that 7(e.g. 2, 3, 5) any ideas?

``````import math
from math import sqrt

x = 1
y = raw_input("What number do you wish to find all the primes below? ")
y = int(y)
while x < y:
a = 2
while a < x:
if x % a == 0:
a = x
elif a == x-1:
if y % a == 0:
a = x
else:
print x
a = x
else:
a = a+1
x = x+1``````

## All 4 Replies

I do not see the connection of you algorithm with being prime, could you write the algorithm you are implementing in pseudo code and mathematical formulas? You are also importing sqrt but not using it (like normally used in primality test).

Sorry I had the sqrt there to make it more efficient but I removed it while debugging. Right now I'm running the code to find all the primes below 1,000,000.
What the program is doing is looking for factors by running through and dividing each number by 2 then 3 then 4 and so on until it reaches the original number. I'll change the variable names, then it will make more sense. This code is a bit more up to date:

``````import math
from math import sqrt

primecount = 1
current = 1
end = raw_input("What number do you wish to find all the primes below? ")
end = int(end)
while current < end: # while loop two
divisor = 2#every number is divisible by 1 so I have to start a 1
z = int(sqrt(current)) + 1#no set of factors has both above it's square makes program effecient
while divisor < current: #while loop number one
if current % divisor == 0: # exits if there is a factor
divisor = current #exits while loop one
elif divisor == current-1: #gives an exit point
if exit % divisor == 0: #Makes sure it's not divisible y one last time
divisor = current #exits while loop one
else:
print current, "The number ", primecount, "prime." #prints prime numbers
divisor = current #exits while loop one
primecount = primecount + 1 #helps count primes
else:
divisor = divisor+1#keeps while loop one going
current = current+1 # move while loop two closer to end``````

If I left any unchanged,
a is divisor
y is exit
x is current

I fixed the code and made it a ton faster, it used to take about 4 hours to find all of them below 1,000,000 but now it takes less than a minute, and it recognizes all primes but 2 and 3. Here is the code:

``````import math
from math import sqrt

b = 1
x = 1
y = raw_input("What number do you wish to find all the primes below? ")
y = int(y)
while x < y:
while x == 2 or x == 3:
print x, "The number", b, "prime."
b = b + 1
x = x + 1
a = 2
z = int(sqrt(x)) + 1
while a < z:
if x % a == 0:
a = x
elif a == z-1:
if x % a == 0:
a = x
else:
print x, "The number", b, "prime."
a = x
b = b + 1
else:
a = a+1
x = x+1``````

Nice that you posted such a original code, even not so hugely fast. I tinkered it slightly to make exits from while normal, skip the even numbers and renamed your variables again by myself. I compared it to another personal implementation of sieve algorithm using generator functions to generate the multiples (not also so efficient as plain sieve). Sieve algorithms are of course much faster (http://www.daniweb.com/software-development/python/code/216871/1502178#post1502178)

``````import time
import itertools

# Returns an iterator for generating all primes < stop.
def primes_gen(stop):
if stop is None:
print("This algorithm doesn't support unbounded ranges")
raise Stop_iteration

# Find all primes by iterating though the candidates and checking
# if each is a known composite (multiple of some prime). _if not, build
# a composite iterator based on it and add it to the heap of iterators
# to check against.
# Based loosely on http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.
md = {}

if key in d:
d[key].append(value)
else:
d[key] = [value]

# This iterator skips all multiples of 2 and 3
# Can apply an optional multiplier
def better_iterator(n, mult = 1):
cycle = itertools.cycle([2, 4])
if (n+1) % 3:
next(cycle)
while True:
yield n * mult
n += next(cycle)

itmaker = better_iterator
it = itmaker(5)
cur = next(it)
yield 2
yield 3
while cur < stop:
if cur in md:
all_iters = md[cur]
del md[cur]
for i in all_iters:
n = next(i)
else:
yield cur
if stop is None or cur*cur < stop:
it2 = itmaker(cur, cur)
n = next(it2)
cur = next(it)

def primes(stop):
limit = candidate = 1
primes_list = []
for candidate in 2, 3:
if candidate < stop:
primes_list.append(candidate)
while candidate < stop:
divisor = 3
if limit * limit < candidate:
limit += 1
while True:
if candidate % divisor == 0:
break
elif divisor >= limit - 1:
if candidate % divisor == 0:
break
else:
primes_list.append(candidate)
break
else:
divisor += 2
candidate += 2
return primes_list

# Runs the function described by the string s, then prints out how long
# it took to run and returns result (added by pyTony)
def timing(s):
t = time.clock()
r = eval(s)
print("%s took %f ms (%i results)." % (s, 1000 * (time.clock() - t), len(r)))
return r

if __name__ == '__main__':
max_prime = 1000000
printing = False
m = len(str(max_prime))
for primefunction in 'primes', 'primes_gen':
print('Using %s upto %i' % (primefunction, max_prime))
pr = timing('list(%s(%s))' % (primefunction, 1000000))
if printing:
print('\n'.join('%6i: %*i' % (ind, m, prime) for ind, prime in enumerate(pr, 1)))

"""Output:
to 01.12.2011 11:54:19,92 K:\test
>primes_hovestar.py
Using primes upto 1000000
list(primes(1000000)) took 20984.728785 ms (78498 results).
Using primes_gen upto 1000000
list(primes_gen(1000000)) took 1960.589405 ms (78498 results).
"""``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.