[항해99] 12일차 알고리즘 , 에라토스테네스의 체

---

항해 99

 

항해 12일차 : 

 

새벽(?) 부터 일어나서 알고리즘 기말고사를봤다.

Queue , Linked list , BFS이런것들 물어보고... 몇개는 잘못대답한것같은데...  어쩔수없지...

그리고나서 컴퓨터 파일정리들도 한번싹하니깐 벌써 열두시가됐다. 

 

그리고 다시 알고리즘 문제를 풀었다.

 

주특기 개별 면담이있었다.

 

 

Youtube: 동빈나:

그리디 + 탐색문제를 +기본 동적 프로그래밍 위주로 풀어라? 

 

https://www.youtube.com/watch?v=ukkLCl9yBvE 

 

백준문제 4948 :

주어진 input 값 : 0 , 1 , 10 ,13 ,100 ,10000 ,100000에대해서 해당하는 소수 개수를 찾는건 가능하다.

시간이 올래걸린다. 

휴... 시간이 오래걸려도 닶을 찾으면 내수준에서 만족할수있을것같은데, 이걸 백준사이트에 넣으면 또 

틀렷다고 나온다, 시간이 오래걸린다고 나오는게아니라... 뭐가 문젤까😦

 

n =int(input())



if n == 1 :
    print(1)
    exit()
elif 0 :
    exit()    

else:

    flag = False 
    count=0
    if n > 0:
        for j in range( n, (2*n)+1):
            j=j+1
            
            if j > 1 :
                for i in range(2, j):
                    if(j%i)==0:
                        flag = True
                        break
                    
            if flag == False:
                count +=1 
            flag = False
            
        print(count)          
            

위에는 뭐가 틀린지 모르겠다.

그래서 새로  에라토스테네스의 체를 이용해서 소수를 구했다. 

 

 

import math

while True :
    n=int(input())
    if n == 0:
        break

    count = 0
    array = [True for i in range(2*n + 1)] 
    for i in range(2, int(math.sqrt(2*n)) + 1): 
        if array[i] :
            j = 2 
            while i * j <= 2*n:
                array[i * j] = False
                j += 1

    for i in range(n+1 , 2*n+1):
        if array[i]:
            count += 1
    print(count)    

 python3 으로 제출 하면시간 초과 라고 나오고 

pyp3로 제출하면 맞는다고 나온다... 머어쩃든 맞앗으니깐 넘어가기로한다.

중요한건  앞으로 소수를 보면 

에라토스테네스의 체를 기억하자.

 

에라토스테네스 밑에서 이해가 확실히 될때까지 계속 읽어보자...

https://freedeveloper.tistory.com/392

[이것이 코딩 테스트다 with Python] 38강 에라토스테네스의 체

백준문제 1929 :

위에 문제에서 에라토스테네스의 체를 공부하고 다른 소수 찾기 문제를 풀어보았다.

왜인지  local 에서 돌릴때 

#a, n = map(int, input().split())

이부분으로 input을 넣을때 실행되지않는다 나만그런건지모르겟다...

 

처음에는  range를  n+1 로 넣엇는데, 안된다 왜안돼는지 모르겟다...

그래서 input값중에서 제일 높은 수로넣었다.

import math
#a, n = map(int, input().split())

a= 1
n= 2
array = [True for i in range(1000001)]
array[0] = False
array[1] = False

for  i in range (2, int(math.sqrt(1000001))+1):

    if array[i] is True:
        j = 2
        while i*j <= n:
            array[i*j] = False
            j += 1


for i in range (a, n+1):
    if array[i] is True:
        print(i)