소수알고리즘 (2) 썸네일형 리스트형 [python] 코딩테스트 대비 - 소수뒤집기 문제) 답안코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import sys #sys.stdin=open("input.txt", "r") def reverse(x):#뒤집은 숫자 리턴 res=0 while x>0: #ex) 120 ㅡ> # 1단계:(t=0 res=0*10+0=0 x=12) # 2단계:(t=2 res=0*10+2=2 x=1) # 3단계:(t=1 res=2*10+1=21 x=0) t=x%10#첫번째 자리수 res=res*10+t#뒤집은 결과 x=x//10#다음 자리 접근 return res def isPrime(x):#소수인지 확인 if x==1:#1은 소수가 아님 return False fo.. [python] 코딩테스트 대비 - 소수(에라토스테네스 체) 문제) 답안 코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys #sys.stdin=open("input.txt","rt") #숫자마다 2부터 시작해서 소수를 체크하는 방식은 시간초과가 발생함. N=int(input()) check=[0]*(N+1)#총 n+1개의 리스트 (인덱스3은 숫자3을 의미) count=0 for i in range(2,N+1):#인덱스 2부터(0 1은 확인할 필요 없음,) N까지 반복 if check[i]==0:#i인덱스가 소수라면 count+=1#카운트 증가 for j in range(i,N+1,i):#i의 배수들은 소수가 아님을 표시 check[j]=1 print(count) Colored by Color Scripter cs 이전 1 다음
