숫자를 한자리씩 옮겨도 모두 소수가 되는 숫자를 circular prime 으로 정의하기로 합니다. 예를 들면, 197은 197, 971, 719 세숫자가 모두 소수입니다.
100 이하의 circular prime 은 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 총 13개가 있다고 합니다.
문제는 100만 이하의 수중에서 위 성질을 만족하는 circular prime의 갯수가 몇개인가 하는것입니다.
100 까지 소수 출력
from sympy import isprime
for i in range(2,101):
if isprime(i):
print(i,"is prime")
2 is prime 3 is prime 5 is prime ... 83 is prime 89 is prime 97 is prime
200까지 소수이면, circular number 생성
from sympy import isprime
for i in range(2,201):
if isprime(i):
print(i,"is prime",end=",")
string = str(i)
is_circular_prime = True
m=len(string)
for i in range(1,m):
string_new = string[i:]+string[:i]
print(string_new,end=",")
print()
Circular number 가 소수인지 확인
from sympy import isprime
for i in range(2,201):
if isprime(i):
print(i,"is prime",end=",")
string = str(i)
is_circular_prime = True
m=len(string)
for i in range(1,m):
string_new = string[i:]+string[:i]
if isprime(int(string_new)):
print(string_new,"is prime",end=",")
else :
print(string_new,"is not prime",end=",")
is_circular_prime = False
print("is_circular_prime ?",is_circular_prime)
2 is prime,is_circular_prime ? True 3 is prime,is_circular_prime ? True 5 is prime,is_circular_prime ? True 7 is prime,is_circular_prime ? True 11 is prime,11 is prime,is_circular_prime ? True 13 is prime,31 is prime,is_circular_prime ? True ... 181 is prime,811 is prime,118 is not prime,is_circular_prime ? False 191 is prime,911 is prime,119 is not prime,is_circular_prime ? False 193 is prime,931 is not prime,319 is not prime,is_circular_prime ? False 197 is prime,971 is prime,719 is prime,is_circular_prime ? True 199 is prime,991 is prime,919 is prime,is_circular_prime ? True
1000 까지 Circular prime 출력
from sympy import isprime
count=0
for i in range(2,1000):
if isprime(i):
#print(i,"is prime",end=",")
string = str(i)
is_circular_prime = True
m=len(string)
for j in range(1,m):
string_new = string[j:]+string[:j]
if not isprime(int(string_new)):
is_circular_prime = False
if is_circular_prime:
print(i,"is circular prime")
count+=1
print(count)
2 is circular prime 3 is circular prime 5 is circular prime 7 is circular prime 11 is circular prime ... 733 is circular prime 919 is circular prime 971 is circular prime 991 is circular prime 25
백만까지 계산
from sympy import isprime
count=0
for i in range(2,1000000):
if isprime(i):
#print(i,"is prime",end=",")
string = str(i)
is_circular_prime = True
m=len(string)
for j in range(1,m):
string_new = string[j:]+string[:j]
if not isprime(int(string_new)):
is_circular_prime = False
if is_circular_prime:
#print(i,"is circular prime")
count+=1
print(count)
55
