코딩묻은 디자이너

https://www.acmicpc.net/problem/11653

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

# 소인수분해

N = int(input())
num = N
factorizaton = []
i = 2
while num > 1:
    if num % i == 0:
        num = num//i
        factorizaton.append(i)
        continue
    i += 1

for i in factorizaton:
    print(i)

N으로 입력값을 받고 num에 N값을 넣어 num 값을 나눠가며 계산했다

지금 생각해보면 그냥 N을 이용했어도 됐을 것 같다

num이 2부터 돌면서 나머지가 0이 되면(나눠지면) factorization리스트에 값을 추가해주고

최종적으로 factorization을 하나씩 출력해줬다

https://www.acmicpc.net/problem/2581

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

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

add = 0
min = 10000
cnt = 0

for sosu in range(M, N+1):
    sosu_check = 0
    for i in range(1,sosu+1):
        if sosu % i == 0:
            sosu_check += 1
    if sosu_check == 2:
        add += sosu
        cnt += 1
        if sosu < min:
            min = sosu
if cnt > 0:
    print(add)
    print(min)
else:
    print(-1)

2021.09.15 - [study/백준] - [백준] 1978번 소수 찾기 : python

이전 소수 찾기와 같은 방법으로 소수를 찾아내고

if 문을 사용해서 add min을 찾아내는 코드를 작성하였다.

예제 입력시 답은 나오는데 시간초과로 틀렸다.

최종코드

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

add = 0
min = 10000
cnt = 0

for sosu in range(M, N+1):
    sosu_check = 0
    if sosu != 1:
        for i in range(2,sosu):
            if sosu % i == 0:
                sosu_check = -1
                break
        if sosu_check == 0:
            add += sosu
            cnt += 1
            if sosu < min:
                min = sosu
if cnt > 0:
    print(add)
    print(min)
else:
    print(-1)

그래서 한번이라도 나머지가 0이 나오면 소수가 아니기 때문에

sosu % i == 0 이 나오면 break되도록 바꿔 주었다.

M 이 1이 들어올 수도 있으니깐 if sosu != 1 해줘야한다. 안그러면 틀린다.

아직 엄청 많은 문제를 풀어본건 아니지만 백준이 swea와 비교했을때 저런 하나의 예외를 잡아야 통과되는 문제가 많은 것 같다. 백준 어렵다

https://www.acmicpc.net/problem/1978

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

# 소수 찾기

N = int(input())
num = list(map(int,input().split()))

sosu = 0
for i in num:
    cnt = 0
    for j in range(1,i+1):
        if i % j == 0:
            cnt += 1
    if cnt == 2:
        sosu += 1

print(sosu)

소수의 개념이 1과 자기자신으로 밖에 나눌 수 없는 수라 j 로 1에서 자기자신까지 돌려서 나머지가 0인 수를 찾아줬다

그리고 나머지가 0인 경우가 2번이면 소수이므로 변수 sosu의 카운트 증가

sosu출력