파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 35번 문제 - Circular Prime

숫자를 한자리씩 옮겨도 모두 소수가 되는 숫자를 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

댓글

댓글 본문
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기