소수찾기

n까지의 정수중 소수의 개수 구하기

생각나는대로 코딩

def solution(n):
    answer = 0
    
    for i in range(2,n+1):
        count = 0
        for j in range(2,i) :
            if i%j==0:
                count+=1
                break
        if count ==0 :
            answer+=1
    return answer

효율성 엄청 떨어짐.

공부하고 만든 코드

def solution(n):
    answer = 0
    
    for i in range(1, n+1) :
        count = 0
        if i<2 :
            continue
        if i==2:
            answer+=1
            continue
        if i%2==0 :
            continue
 
        sr = round(i**0.5)
        for j in range(3, sr+1, 2) :
            if i%j==0 :
                count=1
                break
 
        if count==0 :
            answer+=1
    return answer

1. 2보다 작은 수 무시

2. 2는 소수이므로 answer 증가시키고 다시 진행

3. 2를 제외한 짝수들은 모두 2로 나눠지므로, 모두 무시

4. 소수 판별은 제곱근 까지만 찾아보면 된다.

ex)    100의 약수 1,2,4,5.....50, 100이 있을때, 제곱근인 10까지만 찾아보면 된다.

그 뒤에 나오는 약수인 25, 50같은 경우,

2 * 50

4 * 25이기 때문에 2와 4 같은 작은 수에서 걸러진다.

count변수를 안쓰고 하고 싶었는데, 

제곱근으로 나눠보는 for문(15줄)에서 나눠지는 경우(소수가 아닌 경우)를 제외한 경우가 답이 될 수 없어서 어쩔수 없이 집어 넣음.

  

에라토스테네스의 체

def solution(n):
    num=set(range(2,n+1))
 
    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

.....???

공부하자....

.