파이썬으로 수학문제 풀기- 프로젝트 오일러(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 까지 소수 출력
def is_prime(number):
    i=2
    while i <= number**0.5:
        if number % i == 0:
            return False
        i+=1
    return True

for i in range(2,101):
    if is_prime(i):
        print(i,"is prime")
2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime
53 is prime
59 is prime
61 is prime
67 is prime
71 is prime
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime

 

200까지 소수이면, circular number 생성
def is_prime(number):
    i=2
    while i <= number**0.5:
        if number % i == 0:
            return False
        i+=1
    return True

for i in range(2,201):
    if is_prime(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 가 소수인지 확인
def is_prime(number):
    i=2
    while i <= number**0.5:
        if number % i == 0:
            return False
        i+=1
    return True

for i in range(2,201):
    if is_prime(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 is_prime(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
17 is prime,71 is prime,is_circular_prime ? True
19 is prime,91 is not prime,is_circular_prime ? False
23 is prime,32 is not prime,is_circular_prime ? False
29 is prime,92 is not prime,is_circular_prime ? False
31 is prime,13 is prime,is_circular_prime ? True
37 is prime,73 is prime,is_circular_prime ? True
41 is prime,14 is not prime,is_circular_prime ? False
43 is prime,34 is not prime,is_circular_prime ? False
47 is prime,74 is not prime,is_circular_prime ? False
53 is prime,35 is not prime,is_circular_prime ? False
59 is prime,95 is not prime,is_circular_prime ? False
61 is prime,16 is not prime,is_circular_prime ? False
67 is prime,76 is not prime,is_circular_prime ? False
71 is prime,17 is prime,is_circular_prime ? True
73 is prime,37 is prime,is_circular_prime ? True
79 is prime,97 is prime,is_circular_prime ? True
83 is prime,38 is not prime,is_circular_prime ? False
89 is prime,98 is not prime,is_circular_prime ? False
97 is prime,79 is prime,is_circular_prime ? True
101 is prime,011 is prime,110 is not prime,is_circular_prime ? False
103 is prime,031 is prime,310 is not prime,is_circular_prime ? False
107 is prime,071 is prime,710 is not prime,is_circular_prime ? False
109 is prime,091 is not prime,910 is not prime,is_circular_prime ? False
113 is prime,131 is prime,311 is prime,is_circular_prime ? True
127 is prime,271 is prime,712 is not prime,is_circular_prime ? False
131 is prime,311 is prime,113 is prime,is_circular_prime ? True
137 is prime,371 is not prime,713 is not prime,is_circular_prime ? False
139 is prime,391 is not prime,913 is not prime,is_circular_prime ? False
149 is prime,491 is prime,914 is not prime,is_circular_prime ? False
151 is prime,511 is not prime,115 is not prime,is_circular_prime ? False
157 is prime,571 is prime,715 is not prime,is_circular_prime ? False
163 is prime,631 is prime,316 is not prime,is_circular_prime ? False
167 is prime,671 is not prime,716 is not prime,is_circular_prime ? False
173 is prime,731 is not prime,317 is prime,is_circular_prime ? False
179 is prime,791 is not prime,917 is not prime,is_circular_prime ? False
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 출력
def is_prime(number):
    i=2
    while i <= number**0.5:
        if number % i == 0:
            return False
        i+=1
    return True

count=0
for i in range(2,1000):
    if is_prime(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 is_prime(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
13 is circular prime
17 is circular prime
31 is circular prime
37 is circular prime
71 is circular prime
73 is circular prime
79 is circular prime
97 is circular prime
113 is circular prime
131 is circular prime
197 is circular prime
199 is circular prime
311 is circular prime
337 is circular prime
373 is circular prime
719 is circular prime
733 is circular prime
919 is circular prime
971 is circular prime
991 is circular prime
25

 

백만까지 계산
def is_prime(number):
    i=2
    while i <= number**0.5:
        if number % i == 0:
            return False
        i+=1
    return True

count=0
for i in range(2,1000000):
    if is_prime(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 is_prime(int(string_new)):
                is_circular_prime = False
        if is_circular_prime:
            #print(i,"is circular prime")
            count+=1
print(count)
55

댓글

댓글 본문
작성자
비밀번호
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기