5
\$\begingroup\$

The program below is meant to find all of the fare prime numbers under a user specified value. A fare prime being a number that when its digits are rotated, each combination makes a prime number. An example being 113 because 113, 311, and 131 are all prime numbers. My current problem is that the program takes a very long time to process very large numbers so I need a way of making it run quicker. I've tried to explain the code with the comments but if any part doesn't make sense I'll do my best to explain.

#get user input for the number range
n = int(input("number"))
primes = []
#find all the prime numbers up to the specified value and append them to a list
for num in range(2, n+1):
  for i in range(2, num):
      if num % i == 0:
          break
  else:
     primes.append(num)

#find out if the prime number is a fare prime
for i in primes:
  length = len(str(i))
  #if the number has one digit it is automatically a fare prime
  if length == 1:
    print(i)
  #if the number is longer, rotate the digits to see if it is a fare prime
  if length >= 2:
    number = i
    fare_primes = []
    #rotate the number to figure out if all combinations are prime
    for j in range(length):
      #turns # into a list of digits
      digit_list = list(str(number))
      #rearranges
      number = [*digit_list[1::], digit_list[0]]
      part = ""
      #turns it back into an int value
      number = part.join(number)
      int_num = int(number)
      #check if # is prime
      for divider in range(2,int_num):
        if int_num % divider == 0:
          break
      else:
        fare_primes.append(number)
    #if all combinations of the digits are prime the original # is printed
    if len(fare_primes) == length:
      print(fare_primes[-1])
\$\endgroup\$
2
\$\begingroup\$

A 2+ digit fare prime number can never have an even digit, or a 5 digit in its set of digits, because a rotation which moves an even digit or a 5 to the last digit will be divisible by 2 or 5. You could use that as a filter for your possible fare primes from the list of primes you calculate.

When calculating primes, you can stop at sqrt(num). Any number greater than sqrt(num) that evenly divides num will have a compliment number less than sqrt(num) that you have already tested.

Speaking of primes that you’ve calculated, why don’t you use those for your subsequent prime test? Why try dividing by every number from 2 up to int_num when you could just try the numbers in primes upto int_num.

... or just ask if int_num in primes. Speed tip: turn primes into a set() first for faster inclusion testing.

Your digit_list code is very inefficient. For any number, once you’ve split the number into digits, you don’t need to resplit it into digits again for each rotation. Actually, you don’t even need to split it into individual digits. This will give you the rotated values:

digits = str(i)
for j in range(1, length):
    int_num = int( digits[j:] + digits[:j])
\$\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.