Определить, является ли целое число круговым простым

Я пытался решить проблему Эйлера проекта 35, и мне нужно создать функцию, которая сообщит мне, является ли целое число круговым простым числом. У меня есть стандартная функция isprime и функция, чтобы дать список вращения цифр. Мой код поворота и код iscircularprime здесь:

def rotate(n):
    rotlist = []
    m = str(n)
    counter = 0
    while counter < len(str(n)):
        m = m[1:] + m[0]
        rotlist.append(int(m))
        counter += 1
    return rotlist

def iscircularprime(n):
    np = [0,2,4,5,6,8]
    y = str(n)
    for j in y:
        if int(j) in np:
            return False
    if isprime(n)==False:
        return False
    m = rotate(n)
    for i in m:
        if isprime(i)==True:
            return True
        else:
            return False

Я не включил свою функцию isprime, поскольку она довольно стандартна. Моя функция будет правильно определять, является ли простое число круглым, как в случае с 197, но также идентифицирует некоторые некруглые простые числа как круглые, например 191, которое не является круглым, поскольку 119 не является простым.


python primes
person Dom Wigmore    schedule 01.07.2012    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Вы return True после одного оборота, поэтому не проверяете все круговые простые числа. Вы должны изменить его на:

def iscircularprime(n):
    np = [0,2,4,5,6,8]
    y = str(n)
    for j in y:
        if int(j) in np:
            return False
    if isprime(n)==False:
        return False
    m = rotate(n)

    # new code here
    is_circ_prime = True
    for i in m:
        if not isprime(i):
            is_circ_prime = False
    return is_circ_prime
person mVChr    schedule 01.07.2012
comment
Ах, это полезно, тогда должно быть хорошо, чтобы решить проблему, спасибо за помощь - person Dom Wigmore; 01.07.2012

arrow_upward
0
arrow_downward

Непроверенный, но я думаю, что именно так я решил это много лет назад.

Самый простой способ - быстрый помощник:

from collections import deque
def shifter(num):
 strnum = deque(str(num))
 for i in xrange(len(strnum)):
     yield int(''.join(strnum))
     strnum.rotate()

Затем:

sum(1 for i in xrange(1000000) if all(is_prime(p) for p in shifter(i))
person Jon Clements♦    schedule 01.07.2012

arrow_upward
0
arrow_downward

Вот функция, которая циркулирует любое число:

def circulate_number(A):
  for v in range(len(str(A))):
        a , i , s =  str(A), len(str(A)), ''
        for c in range(i):
              s += str(a[(v+c) % i])
        print(s)
        v+= 1

circulate_number(123456)
person youth4ever    schedule 15.09.2016

arrow_upward
0
arrow_downward

Обязательное неэффективное однострочное решение. Левая часть оператора — первичная проверка, правая — генератор вращений:

from math import factorial as f

def is_circular_prime(n):
    return (lambda s: all(f(i - 1) % i == i - 1 for i in (int(s[j:] + s[:j]) for j in range(len(s)))))(str(n))

for number in range(2, 10000):
    if is_circular_prime(number):
        print(number)

ВЫВОД

> python3 test.py
2
3
5
7
11
13
17
31
37
71
73
79
97
113
131
197
199
311
337
373
719
733
919
971
991
1193
1931
3119
3779
7793
7937
9311
9377
>
person cdlane    schedule 25.12.2018