1.11M Members

Quick debugging

 
0
 

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
 
0
 

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).

 
0
 

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

 
0
 

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
Question Answered as of 2 Years Ago by pyTony
 
0
 

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 = {}

    def add_to_multi_dict(d, key, value):
        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)
                add_to_multi_dict(md, n, i)
        else:
            yield cur
            if stop is None or cur*cur < stop:
                it2 = itmaker(cur, cur)
                n = next(it2)
                add_to_multi_dict(md, n, 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).
"""
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: