[단계별로 풀어보기] - 기본수학 2단계

1978_소수 찾기

⭕풀이:

n = int(input())
numbers = map(int, input().split())
sosu = 0
for num in numbers:
    error = 0
    if num > 1:  #for문을 통해 주어진 numbers의 값들을 반복 중인 num의 값이 1보다 크면(=1이상이 소수의 조건이 되기 때문),
        for i in range(2, num):  #2 ~ num-1만큼 i에 대입해 i가 반복해라.
            if num % i == 0:  #numbers의 값들, 즉 num의 값이 (2 ~ num-1)에 의해 나눠질 경우(소수가 아님),
                error += 1  #error라는 변수에 1을 더해라.
        if error == 0:  #num의 값이 위 for i문과 if문을 거치고, error가 0일 경우(num의 값이 소수일 경우),
            sosu += 1  #sosu라는 변수에 1을 더해라.
print(sosu)

---

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 x in range(2, num):
            if num % x == 0:
                error += 1
                break
        if error == 0:
            sosu_list.append(num)


if len(sosu_list) > 0:
    print(sum(sosu_list))
    print(min(sosu_list))
else:
    print(-1)

---

10653_소인수분해

⭕풀이:

N = int(input())

while N != 1:  #주어진 값 N이 1일때까지 반복해라.(N을 나눌 수 있는 가장 작은 소수 i값을 한번씩 출력한다.)
    i = 2  #i는 가장 작은 소수를 표현한 값이다.
    while True:
        if N % i == 0:  #N을 가장 작은 소수 i값으로 나뉠 경우,
            N = N // i  #N값은 N을 i로 나눈 몫이 된다.
            print(i)
            break  #N값이 더 이상 2로 나눠지지 않는 경우, while TRUE문을 중단하고,
        else:
            i += 1  #i에 1을 더해 다시 while TRUE문을 실행한다.

---

1929_소수 구하기

⭕풀이:

start_num, last_num = map(int, input().split())

for num in range(start_num, last_num+1):
    if num == 1:
        continue  #소수는 1보다 높은 숫자이므로 start_num ~ last_num 범위에 1이 있다면 continue를 통해 아래 코드를 실행하지 않고 건너뛴다.
    for i in range(2, int(num ** 0.5)+1):  #start_num~last_num 사이에서 반복 중인 num의 값이 소수인지 확인하는 방법은
        if num % i == 0:  #num의 제곱근값이나 작은 수까지 num을 나눠보고 나누어 떨어지면은 소수가 아니다.
            break  #그러므로 해당 제곱근 이상의 숫자에 대해 더 이상 검사할 필요가 없으므로 for i문을 멈춘다.
    else:
        print(i)  #그렇지 않고, 나눠지지 않는다면, i를 출력한다.

📌필요지식

1) 소수 구하는 식

• 해당숫자 % (2 ~ 해당숫자의제곱근) == 0 : 소수 x

• 해당숫자 % (2 ~ 해당숫자의제곱근) != 0 : 소수 o

• 해당 숫자의 제곱근을 포함한 1보다 큰 정수로 해당 숫자를 나누었을 때, 나누어 진다면, 해당 숫자를 제곱근보다 큰 숫자로 나눌 필요 없이 해당숫자는 소수가 아니다. 그렇지 않고, 제곱근을 포함한 아래 숫자로 나눠지지 않는다면 해당숫자는 소수다.

2) ** 0.5 연산자

• n ** 0.5 = n의 제곱근
  

---

4948_베르트랑 공준

⭕풀이:

import math

def sosu(num):  #소수찾기 함수
    a = int(math.sqrt(num))  #math.sqrt(num)은 num의 제곱근을 뜻한다.
    if num == 1:  #1은 소수가 될 수 없으므로,
        return False  #1이라는 값에 False값이 주어진다.
    else:
        for i in range(2, a+1):  #2 ~ num의 제곱근 + 1의 범위를 i가 반복해라.
            if num % i == 0:  #num이 num의 제곱근 + 1보다 작은 범위에서 배수가 나올 경우, 소수가 아니다.
                return False  #그러므로 해당 값에 False값이 주어진다.
        return True  #그 밖엔 True값이 주어진다.

Num_list = list(range(2,246912))  #문제의 제한범위이다.
sosu_list = []  #소수를 따로 리스트로 담은 이유는 N과 2N보다 작은 범위로 설정해 while문과 for문을 통해 소수인지 하나씩 무한루프 검사하는 건 시간 초과가 나기 때문에 그래서 아예 주어진 n<=123456값에 모든 소수를 sosu_list에 추가해 리스트 안에 N과 2N사이 소수를 카운트하는 방식을 했다.

for i in Num_list:  #제한범위에서 i를 반복해라.
    if sosu(i):  #제한범위에서 소수를 모두 구하고,
         sosu_list.append(i)  #sosu_list에 제한범위 소수를 모두 넣는다.

while True:
    N = int(input())
    if N == 0:
        break
    cnt = 0
    for i in sosu_list:  #sosu_list는 제한범위내에 있는 소수값들이
        if N < i <= N*2:  #n보다 크고 n*2보다 작거나 같은 수라면
            cnt += 1  #cnt는 cnt + 1이다.
    print(cnt)

⭕풀이설명

• 소수를 따로 리스트로 담은 이유는 N과 2N보다 작은 범위로 설정해 while문과 for문을 통해 소수인지 하나씩 무한루프 검사하는 건(이전 1929_ 소수구하기 방식) 시간 초과가 나기 때문에 그래서 아예 주어진 n<=123456범위에 있는 모든 소수값들을 sosu_list에 넣어 sosu_list 안에서 주어진 입력값 N과 2N사이 소수를 카운트하는 방식을 했다.

---

9020_골드바흐의 추측

⭕첫 번째 풀이:

import math

def sosu(num):  #소수 구하는 함수
    a = int(math.sqrt(num))
    if num == 1:
        return False
    else:
        for i in range(2, a+1):
            if num % i == 0:
                return False
        return True

test_case = int(input())
n_list = [i for i in range(10000) if i % 2 == 0]

for _ in range(test_case):
    n = int(input())
    a = n // 2
    b = n - a
    while True:
        if sosu(a):
            if sosu(b):
                print(b, a)
                break
        else:
            a += 1
            b -= 1

처음 풀이는 소수를 구하는 함수 sosu()를 만들어 둔 뒤,
골드바흐의 파티션의 두 소수의 차가 가장 적게 나야 하기 때문에
우선 주어진 입력값 n을 2로 나눈 값을 a로 변수선언하고, n - a을 b로 변수선언했습니다.
그 뒤, a의 값이 소수이고 b의 값 또한 소수인 경우
출력했습니다.
그렇지 않고 a가 소수이지 않다면, a에 1을 더하고 b에서 1을 빼는 방식으로 서로가 소수가 될 때까지 while문을 통해 무한루프를 돌렸는데
역시 시간초과가 났습니다..

⭕풀이:

import math

def sosu(num):  ##소수 구하는 함수
    a = int(math.sqrt(num))
    if num == 1:
        return False
    else:
        for i in range(2, a+1):
            if num % i == 0:
                return False
        return True

test_case = int(input())

for _ in range(test_case):
    n = int(input())
    for a in range(n // 2, 0, -1):  #주어진 입력값 n을 2로 나눈 값에서 0까지 내림차순으로 반복해라.
        if sosu(a) and sosu(n - a):  #n을 2로 나누 값에서 내림차순으로 반복하다 소수인 a값이 있고, n에서 a를 뺀 나머지 값 또한 소수일 경우, 
            print(a, n - a) 
            break

간단했습니다. 접근은 맞았는데, 조금 더 쉽게 표현하기 위해 for문의 역순을 이용해 시간초과를 통과했습니다.

📌필요지식

1) for문의 역순

• for x in range(범위 시작 부분, 범위 끝나는 부분, -1)
  
  

---