소수 찾기,소수 구하기 백준 1978번, 1929번 수학

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

문제는 소수찾기이기에 설명도 생략하겠습니다.

소수의 정의는 1과 자기자신 이외로는 나누어지지 않는 수를 뜻합니다. 정의에 따라서 1은 소수도 합성수도 아닙니다.

여기서 소수를 n-1까지 모두 나누어서 확인해보는 대신 제곱근까지만 확인해도 소수임을 판별할 수 있으니 소수를 판별하는 함수를 따로 만들고 이를 통과하는 조건문을 걸어서 소수의 개수를 세면 됩니다.

import math

def func(x):
    if x==1:
        return False
    temp = int(math.sqrt(x))
    for i in range(2,temp+1):
        if x%i == 0:
            return False
    return True

num = int(input())
num_list = list(map(int,input().split()))
ans = 0
for i in range(num):
    if func(num_list[i]):
        ans+=1
print(ans)

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

이어서 소수 찾기 문제를 하나더 봅시다. 푸는 로직은 똑같으니 소수를 구하는 함수는 그대로 재사용 합니다.

import math

def func(x):
    if x==1:
        return False
    temp = int(math.sqrt(x))
    for i in range(2,temp+1):
        if x%i == 0:
            return False
    return True

n,m = map(int,input().split())
for i in range(n,m+1):
    if func(i):
        print(i)

주어진 n부터 m까지 소수인지 확인을 하면 됬습니다. 다만 여기서 에라토스테네스의 체를 사용해서 한번 문제를 풀어 봤습니다.

import math

def func(x):
    if x==1:
        return False
    temp = int(math.sqrt(x))
    for i in range(2,temp+1):
        if x%i == 0:
            return False
    return True

n,m = map(int,input().split())
bool_list = [False]*(m+1)
for i in range(n,m+1):
    if not bool_list[i] and func(i):
        bool_list[i]=True
        print(i)
        temp = 2
        while True:
            if i*temp>=m:
                break
            bool_list[i*temp]=False
            temp+=1

제가 로직을 잘못 짠건지

걸리는 시간이 약간 늘어나있네요 메모리는 소수를 확인하기 위한 bool을 추가 했으니 당연한거고요