Circular Primes

[Thisisnotanid]

Hi everyone. I was trying to solve Pb 35 on Project Euler (http://projecteuler.net/index.php?section=problems&id=35). It essentially asks to write a program to list all circular primes under 1e6. I wrote the program and it works well for the most part. However, in the end it seems not to be able to conduct membership tests properly. For example, it lists 391 as a prime. I have looked it over and over but I can't figure out what's wrong. I will probably also try a new approach, but I want to know why this doesn't work. I am new to programming, so please forgive me if it's a newbie error. I used Python 2.7, the code follows:

def numrotator(pStr):
	s=pStr
	a = [] # Contains all the rotated integers
	b = [] # Contains the rotated integer for one iteration
	for i in range(0, len(s)):
		for x in range(len(s) - 1, -1, -1): # Rotation algorithm
			b.append(s[i-x]) 
		a.append(b)
		b = []
	a.reverse() # Prime is listed first.
	c = []
	for i in a: # Convert strings to integers.
		p = ''
		for l in i:
			p += l
		p = int(p)
		c.append(p)
	return c

def pLister():
	# Euler's Sieve implementation. Removes multiples of numbers by removing numbers at the positions where the multiples will be.
	n = int(raw_input("Num: "))  # Upper range.

	s = range(3, n+1, 2)  # Only odds are checked..

	i = 1 

	a = len(s) - 1

	for l in range(0, a + 1): 
		a1 = i
		j = (l + (s[l]*i))
		while (j <= a) and s[l] != 0: 
			s[j] = 0
			i += 1 
			j = (l + (s[l]*i)) 
		i = a1 + 1 # Avoid double checking. For example, since 3*7 gets removed first, the algorithm skips 7*3.

	s = list(set(s))
	s.sort()
	s.remove(0)
	s = [2] + s
	return s	
	
s2 = pLister()
s2.sort()

def dConstructor(s1):
	d=[]

	for i in s1:
		i = str(i)
		if '2' not in i and '4' not in i and '5' not in i and '6' not in i and '8' not in i and '0' not in i:
				d.append(numrotator(i)) # Only numbers without 2,4,5,6,8, or 0 are rotated since numbers
			                            # containing those digits will be composite in at least one rotation.
	for i in d:
		i.sort()
		
	d.sort()
	
	for i in d: # Here's where I think the problem lies (The entire loop)
		for l in i:
			if l not in s1:
				while i in d:
					d.remove(i)
	return len(d) + 2 # If the algorithm works as it should, lists containing circular primes would appear as many times as the number of digits in one circular prime.

print dConstructor(s2)

[TrustyTony]

I have not time to debug for you, but I quickly hacked together this my version from my archive, at least it got under 100 cases right even it took over 8 seconds for case 1000000 to get 55 cases:

import time
def numrotator(number):
    string_number=str(number)
    return [int(string_number[place:]+string_number[:place]) for place in range(len(string_number))]
    
def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def circular_prime(primes):
    for prime in primes:
        if (prime<10 or not any( c in '245680' for c in str(prime))) and all(num in primes for num in numrotator(prime)):
            yield prime
            
t0 = time.time()
for count, prime in enumerate(circular_prime(rwh_primes1(1000000))):
    print '%6i: %i' % (count+1, prime)

print '='*60
print 'Total = %i' % (count+1)
print 'Time: %.3f s' % (time.time()-t0)

[richieking]

Not bad ;)

[Thisisnotanid]

I have not time to debug for you, but I quickly hacked together this my version from my archive, at least it got under 100 cases right even it took over 8 seconds for case 1000000 to get 55 cases:

import time
def numrotator(number):
    string_number=str(number)
    return [int(string_number[place:]+string_number[:place]) for place in range(len(string_number))]
    
def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def circular_prime(primes):
    for prime in primes:
        if (prime<10 or not any( c in '245680' for c in str(prime))) and all(num in primes for num in numrotator(prime)):
            yield prime
            
t0 = time.time()
for count, prime in enumerate(circular_prime(rwh_primes1(1000000))):
    print '%6i: %i' % (count+1, prime)

print '='*60
print 'Total = %i' % (count+1)
print 'Time: %.3f s' % (time.time()-t0)

Tony, I'm not sure as to how a lot of your code works. Some of the syntax is unfamiliar to me, for example. As I said, I'm new to programming and Python is my first language. Can you please explain some of your code, the logic behind it, or present a sketch of how you approached the problem? Any help will be appreciated, thanks!

[Thisisnotanid]

Hi everyone. I figured what was wrong. For some reason, the for loops for removing primes with 2, 4, 5, 6, 8, or 0 in them was checking every other number in the list of primes. I fixed the problem, the solutions works now, and works sufficiently fast as well! Also, I've changed my approach by a lot compared to what I did in my original solution. Here it is:

def numrotator(pStr):
	s=pStr
	a = [] # Contains all the rotated integers
	b = [] # Contains the rotated integer for one iteration
	for i in range(0, len(s)):
		for x in range(len(s) - 1, -1, -1): # Rotation algorithm
			b.append(s[i-x]) 
		a.append(b)
		b = []
	a.reverse() # Prime is listed first.
	c = []
	for i in a: # Convert strings to integers.
		p = ''
		for l in i:
			p += l
		p = int(p)
		c.append(p)
	return c

def pLister():
	# Euler's Sieve implementation. Removes multiples of numbers by removing numbers at the positions where the multiples will be.
	n = int(raw_input("Num: "))  # Upper range.

	s = range(3, n+1, 2)  # Only odds are checked.

	i = 1 

	a = len(s) - 1

	for l in range(0, a + 1): 
		a1 = i
		j = (l + (s[l]*i))
		while (j <= a) and s[l] != 0: 
			s[j] = 0
			i += 1 
			j = (l + (s[l]*i)) 
		i = a1 + 1 # Avoid double checking. For example, since 3*7 gets removed first, the algorithm skips 7*3.

	s = list(set(s))
	s.sort()
	s.remove(0)
	s = [2] + s
	return s	
	
s2 = pLister()
s2.sort()

s2len = len(s2)
for i in range(0, s2len):
	s2iStr = str(s2[i])
	for l in s2iStr:
		if l in '245680':
			s2[i] = 0
s2 = list(set(s2))
s2.remove(0)
s2.sort()


def dConstructor(s1):
	d=[]
	s1 = set(s1)
	cpS = 2
	for i in s1:
		i = str(i)
		d = numrotator(i) 
		d = set(d)
		inter = s1 & d
		if len(inter) == len(d):
			cpS += len(d)
		s1 = s1 - d
		

	return cpS # If the algorithm works as it should, lists containing circular primes would appear as many times as the number of digits in one circular prime.

print dConstructor(s2)

[TrustyTony]

Nice use of set operations, maybe you should clarify the naming of variables, though. Also I would prefer not to special casing the 2 and 5 as starting value 2 for cpS. I would not use the mixed case names also, but at least you are not using capitalized camel case.

Here is my code using set operations like yours, running time cut to half second in my computer:

import time
def numrotator(number):
    string_number=str(number)
    return set([int(string_number[place:]+string_number[:place]) for place in range(len(string_number))])
    
def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def circular_primes(primes):
    """ yield the rotations of circular primes in primes as set """
    not_these = set('245680')
    primes_left = set([prime
                       for prime in primes
                       if (prime<10 or
                           not (not_these & set(str(prime))))])
    # sorted produce copy as list from primes_left    
    for candidate in sorted(primes_left):
        # check that candidate was not removed from original
        if candidate in primes_left:
            d = numrotator(candidate)
            inter = primes_left & d
            primes_left -= d
            if inter == d:
                yield d

def circular_prime_count(primes):
    return sum(map(len,circular_primes(primes)))
           
t0 = time.time()
print 'Total = %i' % (circular_prime_count(rwh_primes1(1000000)))
print 'Time: %.3f s' % (time.time()-t0)

[Thisisnotanid]

Cool, nicely done.