[python] 단계별로 풀어보기 - 9단계(1~6)

 

 

 

 

 

8단계가 어려워서 9단계 먼저 풀기 !

사실 9단계 문제도 많아서 나눠서 풀기!

 

 

---

 

 

 

9-1) 백준 1978번: 소수 찾기

 

M = int(input())
a = list(map(int, input().split()))
num_count = 0

for i in a:
    count = 0
    if i == 1:
        continue
        
    for j in range(2, i+1):
        if i % j  == 0:
            count += 1

    if count == 1:
        num_count += 1
        
print(num_count)

 

수를 입력받아 리스트에 저장하고, 반복문을 통해 수를 하나하나 꺼내보며 소수인지 아닌지 구분한다.

소수는 1과 자기 자신만으로만 나눠지는 수이므로,

2부터 자신에 해당하는 수까지 반복하며 나눠서 나머지가 0이라면 count +1을 해준다.

최종적으로, count=1이라면 자기 자신으로만 나눴을 때 나누어떨어진 것 이므로 num_count +1을 해준다.

​

​

​

​

 

9-2) 백준 2581번: 소수

 

M = int(input())
N = int(input())

num_list = []

for i in range(M, N+1):
    count = 0
        
    for j in range(2, i+1):
        if i % j  == 0:
            count += 1

    if count == 1:
        num_list.append(i)

if len(num_list) == 0:
    print("-1")
else:
    print(sum(num_list))
    print(min(num_list))

 

위와 유사한 방법을 사용하는데, 범위를 수정해주고 count가 1인 소수의 개수를 세는 것이 아니라

해당하는 값을 num_list에 넣어준다.

그 후 최종적으로 합과 최솟값 출력

​

 

​

​

 

9-3) 백준 11653번: 소인수분해

 

M = int(input())

while M != 1:
    for i in range(2, M+1):
        if M % i ==0:
           print(i)
           M = M//i
           break

 

while반복문을 사용해서 1이 될때까지 만들어주고,계속 수를 더해가며 나눠준다.

나누어떨어진다면 그 수 출력해주기

​

​

​

 

​

​

9-4) 백준 1929번: 소수 구하기

 

def isPrime(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N+1):
    if isPrime(i):
        print(i)

 

에라토스테네스의 체 개념 사용

확실히 소수 찾는 속도가 빨라지는 것이 느껴졌음

​

 

* 라토스테네스의 체

에라토스테네스의 체: 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

 

1. 1을 제거

2. 지워지지 않는 수 중 제일 작은 수 2를 소수로 채택하고, 나머지 2의 배수 모두 지우기

3. 지워지지 않는 수 중 2 다음으로 작은 수인 3을 채택하고, 나머지 3의 배수 모두 지우기

4. 지워지지 않는 수 중 3 다음으로 작은 수인 5를 채택하고, 나머지 5의 배수 모두 지우기

...

​

​

​

​

 

​

9-5) 백준 4948번: 베스트랑 공준

 

밑의 코드는 시간초과가 뜬 코드

 

def isPrime(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

M = int(input())
cnt = 0

while M !=0:
    for i in range(M+1, 2*M+1):
        if isPrime(i):
            cnt +=1           
    print(cnt)
    cnt = 0
    M = int(input())

 

에라토스테네스의 체 개념을 사용 하고, 범위를 지정해준 뒤 그만큼 반복문을 돌며 소수인지 확인.

소수이면 cnt+1해주고 마지막에 출력했는데......계속 시간초과가 떴다............ :(

 

 

 

그래서 아무리 고민해도 계속 오류나길래 구글링해보니까

주어진 범위만큼 따로 소수만 모아두는 리스트를 따로 만들어두고,

나중에 값을 입력받으면 범위에 해당하는 수를 세서 출력하는 방법을 주로 사용하는 것을 발견함

​

저 방법이 더 오래 걸릴 줄 알았는데... 아니었다..........

 

 

 

하단의 코드는 성공한 코드

 

def isPrime(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True
    
a = list(range(2, 246912))
b = []
for i in a:
    if isPrime(i):
        b.append(i)

M = int(input())
cnt = 0

while M !=0:
    for i in b:
        if M < i < M*2+1:
            cnt += 1
    print(cnt)
    cnt = 0
    M = int(input())

 

 

 

 

 

 

 

9-6) 백준 9020번: 골드바흐의 추측

 

prime_list = [False, False] + [True]*10002

for i in range(2, 10001):
    if prime_list[i]:
        for j in range(2*i, 10001, i):
            prime_list[j] = False

T = int(input())

for i in range(T):
    n = int(input())
    a = n//2
    b = a
    while a>0:
        if prime_list[a] and prime_list[b]:
            print(a, b)
            break
        else:
            a-=1
            b+=1

 

위의 문제와 비슷하게 먼저 리스트를 만들어 둔 뒤, 값을 찾아나간다.

또한, 두 소수의 차이가 가장 작은 것을 출력해야하므로 입력받은 값을 2로 나눈 몫을 기준으로 옮겨가며 수 찾기

​

​