1978번
소수, prime number : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
num을 나눈 수가 자기자신인 경우를 제외해야 한다. (num ≠ i)
N = int(input()) # 9
numList = list(map(int, input().split())) # 1 2 3 4 5 6 7 8 9
for num in numList:
if num == 1: #숫자 1은 소수가 아니다. # 1
N -= 1
else: #2부터 숫자를 나눠보고, 해당 숫자로 나눠 떨어지면 소수가 아니다. # 2 3 4 5 6 7 8 9
for i in range(2, num):
if num % i == 0 and num != i: # 소수가 아닌 수: 4 6 8
N -= 1
break
print(N) # 5 (2 3 5 7 9)
https://ko.wikipedia.org/wiki/소수_(수론)
M = int(input())
N = int(input())
numList = list(map(int, range(M,N+1)))
for num in range(M, N+1):
if num == 1: #숫자 1은 소수가 아니다.
numList.remove(num)
else: #2부터 숫자를 나눠보고, 해당 숫자로 나눠 떨어지면 소수이다.
for i in range(2, num):
if num % i == 0:
numList.remove(num)
break
result = sum(numList)
if result == 0:
print('-1')
else:
print( result )
print( numList[0] )
import sys
N = int(sys.stdin.readline())
num = 2
while True:
if N % num == 0:
N = N // num
print(num)
else:
num += 1
if N == 1:
break
1929번
처음 풀었던 코드는 정답은 잘 출력되나, 시간초과로 실패함
'에라토스테네스의 체'를 이용하여 다시 품 (자료 참고함)
문제분석
def prime_list(M, N) -> list:
sieve = [True]*(N+1)
if M == 1 and N == 1:
return []
for i in range(2, N+1):
if sieve[i] == True:
for j in range(i+i, N+1, i):
sieve[j] = False
sieve[1] = False
true = [ x for x in range(M,N+1) if sieve[x] == True ]
return true
M, N = map(int, input().split())
list = prime_list(M,N)
for num in list:
print(num)
https://ko.wikipedia.org/wiki/소수_(수론)
https://ko.wikipedia.org/wiki/에라토스테네스의_체
def prime_list(M, N) -> int:
sieve = [True]*(N+1)
if M == 1 and N == 1:
return []
for i in range(2, N+1):
if sieve[i] == True:
for j in range(i+i, N+1, i):
sieve[j] = False
sieve[1] = False
true = [ x for x in range(M+1,N+1) if sieve[x] == True ] #M값(n)보다 커야하므로 +1을 해준다.
return len(true)
while True:
n = int(input())
if n == 0:
break
print( prime_list(n, 2*n) )
def prime_list(N) -> list:
sieve = [True]*(N+1) #N은 4보다 크고, 10000보다 작은 수가 들어온다.
for i in range(2, N+1):
if sieve[i] == True:
for j in range(i+i, N+1, i):
sieve[j] = False
true = [ x for x in range(2,N+1) if sieve[x] == True ]
return true
T = int(input())
for i in range(T):
n = int(input())
prime = prime_list(n)
a = b = n//2
while True:
if a in prime and b in prime:
print(a, b)
break
else:
a -= 1
b += 1