백준 1929 풀이 (에라토스테네스의 체)

음 처음에 알고리즘 이름이 너무 길어서 쫄았다. 

그래서 검색을 통해 알아보니 소수를 구하기 위한 방식이었다.

 

1. N 을 나눌경우 몇까지 나눌수 있는지 구한다.

=> Max_division = N ** 0.5

2. N을 2~Max_division까지 나누면서 떨어지는지 판별한다. 

3. 만약 N과 값이 같거나 나누어 떨어지지 않으면 소수로 판별한다.

 

문제는 어떻게 풀어도 시간초과로 뜬다. 그래서 다른 사람들 풀이를 보니 함수로 만들어서 식을 더 최소화 시키는 방법을 적용하는 것을 알게되었다.

a,b = map(int,input().split())
for val in range(a,b+1):
    flag = 1
    for i in range(2,int(val ** 0.5)+1):
        if val == 1:
            flag = 0
            break
        elif val % i == 0:
            flag = 0
            break
    if flag == 1 :
        print(val)

 

다른 사람의 코드를 보고 참고하여 최대한 간결하게 풀어보았다. 시간초과가 나왔던 내 코드의 단점은 불필요한 연산이 중간 중간 들어갔다는 점 이었던거 같다.

a,b = map(int,input().split())

def check(num):
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return 0
    return 1*(num!=1)#num!=1을 통해 1이 아님을 확인한다.

for val in range(a,b+1):
    if check(val):
        print(val)