[8단계] 기본수학 2
1978번. 소수찾기
▼해설보기
n = int(input())
numbers = map(int, input().split())
sosu = 0
for num in numbers:
error = 0
if num > 1 :
for i in range(2, num): # 2부터 n-1까지
if num % i == 0:
error += 1 # 2부터 n-1까지 나눈 나머지가 0이면 error가 증가
if error == 0:
sosu += 1 # error가 없으면 소수.
print(sosu)1. 코드에 대한 전체적인 내용 풀이
소수 : 1과 자기 자신으로 나눌 때만 나누어 떨어지는 자연수이다. 1은 소수가 아니고 2는 소수 중에 유일한 짝수이다.
2를 제외한 나머지 소수는 모두 홀수로 이루어져 있다. (예 : 2, 3, 5, 7, 11...)
이 문제는 n개의 숫자가 주어지면 그중 소수인 숫자가 몇 개인지를 출력하는 문제이다. 입력받은 숫자들 중 소수인 수를 찾아내는 방식으로 문제를 풀었다. 소수를 판별하기 위해서 각 숫자가 1부터 해당 숫자까지의 숫자 범위에서 1과 자기 자신을 제외한 수로 나누어 떨어지는지 여부를 if 조건식을 이용해서 찾아냈다.
2. 코드 상단부, 숫자를 입력받는다.
n = int(input())
numbers = map(int, input().split())먼저 숫자의 개수 n을 입력받고 그다음에 숫자 n개의 숫자들을 공백으로 구분한 하나의 문자열로 입력받는다.
문자열로 입력받은 n개의 수는 split을 이용하여 공백을 기준으로 나누고서 map 함수를 이용해서 int로 변환하였다.
이 숫자들은 numbers 변수에 선언하였다. 그리고 이 문제를 풀 때 맨 처음 입력받은 숫자 n은 사용하지 않았다.
3. 소수인지 아닌지 찾아내는 코드를 작성한다.
sosu = 0
for num in numbers:
error = 0
if num > 1 :
for i in range(2, num): # 2부터 n-1까지
if num % i == 0:
error += 1 # 2부터 n-1까지 나눈 나머지가 0이면 error가 증가
if error == 0:
sosu += 1 # error가 없으면 소수.첫 번째 for문으로 numbers 변수에 있는 숫자들을 하나씩 num변수에 선언하였다. 그리고 num의 수가 1보다 큰 경우 2번째 for문에서 생성된 변수 i를 나누어서 0으로 나누어 떨어지는지를 확인하였다. 이때 두 번째 for문의 숫자 범위는 2부터 num-1까지의 범위이다.1과 자기 자신을 제외한 숫자로 나누었을 때 0으로 나누어 떨어지면 error 변수에 1을 더해주었다. 이후 2번째 반복문이 끝나고서 error 변수가 0이면 1과 자기 자신을 제외한 숫자로는 나누어 떨어지지 않은 것이므로 소수가 된다. 소수인 경우 sosu 변수에 1을 추가해서 for문이 모두 끝난 후 sosu 변수를 출력하였다. error변수는 첫 번째 for문이 시작될 때마다 0으로 선언하였다.
2581번. 소수
▼해설보기
start_num = int(input())
last_num = int(input())
sosu_list = []
for num in range(start_num, last_num+1):
error = 0
if num > 1 :
for i in range(2, num): # 2부터 num-1까지
if num % i == 0:
error += 1
break # 2부터 num-1까지 나눈 몫이 0이면 error가 증가하고 for문을 끝냄
if error == 0:
sosu_list.append(num) # error가 없으면 소수리스트에 추가
if len(sosu_list) > 0 :
print(sum(sosu_list))
print(min(sosu_list))
else:
print(-1)1. 코드에 대한 전체적인 내용 풀이
이번 문제는 숫자의 범위가 주어지면 소수를 구하고서 소수들의 합과 최솟값을 출력하는 문제이다. 만일 소수가 없다면 -1을 출력해야 한다. 이번 문제를 풀 때는 주어진 문제에 대해서 직관적으로 코드로 작성했다. 먼저 숫자 범위를 먼저 생성하고서 반복문을 이용해서 숫자를 꺼낼 때마다 1과 자기 자신을 제외한 수를 하나하나 나눠서 나누어 떨어지는 수가 없으면 소수 리스트에 더해가는 방식으로 풀었다.
2. 코드 중반부, 소수를 구하는 코드를 작성한다.
sosu_list = []
for num in range(start_num, last_num+1):
error = 0
if num > 1 :
for i in range(2, num): # 2부터 num-1까지
if num % i == 0:
error += 1
break # 2부터 num-1까지 나눈 몫이 0이면 error가 증가하고 for문을 끝냄
if error == 0:
sosu_list.append(num) # error가 없으면 소수리스트에 추가소수를 판별하기 위해서 반복문을 포함한 반복문 코드를 작성하여 두 개의 숫자 범위가 반복할 수 있도록 했다. 첫 번째 숫자 범위는 입력받은 두 수의 범위이다. 변수 이름은 start_num, last_num으로 지정하였다. 그리고 두 번째 숫자 범위는 상위 for문에서 생성된 num 변수의 숫자를 나눌 숫자이다. 1과 num변수 사이의 숫자로 변수 이름은 i로 정하였다. num변수가 1보다 큰 경우 num과 i를 나누어서 나머지가 0인 경우 소수가 아니므로 error 변수에 1을 더해주었다. 하위 for문이 모두 끝나고서 error 변수가 0이면 소수이므로 이 수를 append 함수로 리스트에 추가하였다.
3. 코드 하단부, 출력문을 작성한다.
if len(sosu_list) > 0 :
print(sum(sosu_list))
print(min(sosu_list))
else:
print(-1)if 조건식을 이용해서 위에서 생성한 소수 리스트의 원소 개수가 0보다 크면 소수의 합과 최솟값을 출력하고 0이면 -1을 출력한다. 소수의 합을 구할 때는 sum 함수, 최솟값을 구할 때는 min함수를 사용하였다.
11653. 소인수분해
▼해설보기
n = int(input())
i = 2
while n!=1:
if n%i == 0:
print(i)
n = n/i
else:
i+=1
1929번. 소수구하기
▼해설보기
n, m = map(int,input().split())
prime_list = [True] * (m+1)
prime_list[0] = False
prime_list[1] = False
for i in range(2,int(m**0.5)+1):
if prime_list [i]:
for j in range(i*2, m+1, i):
prime_list[j]=False
for i in range(n,m+1):
if prime_list[i] :
print(i)1. 코드에 대한 전체적인 내용풀이
에라토스테네스의 체를 사용하여 소수 구하기 문제를 풀었다. 에라토스테네스의 체란 일정 범위 내 수열에서 배수들을 제거해 소수만 걸러내는 방법으로 범위의 제곱근까지만 약수 여부를 검증하는 방식이다. 이렇게 되면 O(N)이었던 시간복잡도가 O(N^(1/2))로 줄어들게 된다.
2. m+1개의 [True]가 있는 prime_list를 생성한다.
prime_list = [True] * (m+1)
prime_list[0] = False
prime_list[1] = Falsem+1개의 [True]가 있는 prime_list를 생성 후 0번째, 1번째 자리 즉 숫자 1,2 는 소수가 아니기 때문에 False 처리한다.
3. for문을 통해 소수가 아닌 수를 j로 치환 후 False 처리한다.
for i in range(2,int(m**0.5)+1):
if prime_list [i]:
for j in range(i*2, m+1, i):
prime_list[j]=Falsem 제곱근 작성 시 int 함수를 통해 리스트형으로 저장되었던 m을 숫자형으로 바꾸어준다.
이후, prime_list에 저장되어있던 i를 하나씩 꺼낸 후, m+1 직전까지의 i*2의 배수들을 모두 j로 바꾸고 False 처리한다.
4.for문을 통해 소수를 출력한다.
for i in range(n,m+1):
if prime_list[i] :
print(i)prime_list에 저장되어있는 i 들을 출력한다. (소수가 아닌 수들은 j로 치환 후 False처리 완료)
4948번. 베르트랑 공준
▼해설보기
num = []
for i in range(2, 246913):
cnt = 0
for p in range(2, int(i**0.5)+1):
if i % p == 0:
cnt += 1
break
if cnt == 0:
num.append(i)
while True:
n = int(input())
res = 0
if n == 0:
break
for i in num:
if n < i <= 2*n:
res += 1
print(res)1. for문 문제풀이
i 나누기 p의 나머지가 0이라면 1씩 증가시키고 멈춘다. 하지만 만약 cnt = 0 이라면 num 리스트에 i를 추가한다.
2.while문 문제풀이
만약 num 리스트에 있는 i 가 n < i <2n 의 범위에 해당한다면 res 수를 1씩 증가시킨 후 출력한다.
9020번. 골드바흐의 추측
▼해설보기
def is_prime(n):
if n == 1:
return False
for j in range(2, int(n**0.5) + 1):
if n % j == 0:
return False
return True
for _ in range(int(input())):
num = int(input())
a, b = num//2, num//2
while a > 0:
if is_prime(a) and is_prime(b):
print(a, b)
break
else:
a -= 1
b += 1