3
\$\begingroup\$

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Here's my implementation in Python 3. Awaiting feedback.

from time import time


def is_prime(number):
    """returns True for a prime number, False otherwise."""
    factor = 2
    while factor * factor <= number:
        if number % factor == 0:
            return False
        factor += 1
    return True


def circulate(number):
    """returns all circulations of a number."""
    for n in str(number):
        if not int(n) % 2:
            return False
    circulations = []
    digits = list(str(number))
    for i in range(len(str(number))):
        last = digits.pop()
        circulations.append(last + ''.join(digits))
        digits = [last] + digits
    return [int(x) for x in circulations]


def circular_primes(limit):
    """returns all circular primes below limit."""
    all_circulations = [2]
    for num in range(3, limit, 2):
        if is_prime(num):
            check = 0
            if circulate(num):
                circulations = circulate(num)
                for circulation in circulations:
                    if not is_prime(circulation):
                        check += 1
                if not check:
                    all_circulations.extend(circulations)
    return all_circulations


if __name__ == '__main__':
    start_time = time()
    print(len(set(circular_primes(200000))))
    print(f'Time: {time() - start_time} seconds.')
\$\endgroup\$
  • 1
    \$\begingroup\$ If you add the tag beginner to your posts, reviewers should be aware of your lack of experience and should review your code from a different perspective: codereview.stackexchange.com/questions/tagged/beginner. \$\endgroup\$ – dfhwze Jul 22 at 10:03
  • 1
    \$\begingroup\$ The problem is i got several consecutive unexplained downvotes for no apparent reasons, code does what it is created for in a timely manner and a downvote is misleading without a feedback. I'll add the tag in future posts anyway. \$\endgroup\$ – emadboctor Jul 22 at 10:08
  • 3
    \$\begingroup\$ I noticed at one point you were asking question after question after question every 2 hours. And someone gently suggested you to take a little break :) Perhaps you should take a bit more time for each question, focus on quality rather than quantity. What do you think? \$\endgroup\$ – dfhwze Jul 22 at 10:15
  • 3
    \$\begingroup\$ I found this post which might be interesting for you: codereview.meta.stackexchange.com/questions/590/… \$\endgroup\$ – dfhwze Jul 22 at 10:19
  • 2
    \$\begingroup\$ One of the problems people may have with your questions, is you won't learn as much by rushing through the exercises and posting multiple on the same day. After all, you'll be making the same mistake over and over before it gets reviewed. \$\endgroup\$ – Mast Jul 22 at 11:06
2
\$\begingroup\$

Let's start with a quick analysis of your current algorithm. For each number less than n (1000000 in your case) it does sqrt(n)log(n) operations (sqrt for is_prime*logcycles). However, some fairly simple things about this problem make it much easier to solve.

As you probably know, any 2 digit or greater number ending in 2,4,6,8 or 5 is not prime since it is divisible by 2 or 5. Thus when constructing circular primes, you don't even have to check numbers that have these digits in them (and add 2 to the result for 2,5)

Thus by changing the main bit of code to only generate reasonable candidates, you do significantly less work.

def digit_combinations(digit_list, n):
    if n == 1:
        for digit in digit_list:
            yield digit
        return
    for digit in digit_list:
        for part in digit_combinations(digit_list, n-1):
            yield digit + 10*part


def circular_primes(digits):
    if digits == 1:
        return 4 # 2,3,5,7

    all_circulations = [2,3,5,7]
    for i in range(2, digits):
        for num in digit_combinations((1,3,7,9), i):
            if is_prime(num):
                check = 0
                if circulate(num):
                    circulations = circulate(num)
                    for circulation in circulations:
                        if not is_prime(circulation):
                            check += 1
                    if not check:
                        all_circulations.extend(circulations)
    return all_circulations

By my timings, this code can return the 8 digit or less ones in 3 seconds, where yours took 7 seconds to do only up to 1 million.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.