C언어 소수 찾는 알고리즘 좀 봐줄래양?

N을 입력받으면 반복문을 루트N만큼 반복해서
1부터N까지 소수를 전부 출력하는걸 짜라는데

N이 100이라 치면 출력하는데만 반복문 24번 돌고
출력하는거 제외한다 쳐도

에라테스토너스 써도 무조건 반복문이 10번 무조건
넘겨버리는데
여기서 이진탐색 개념을 어떻게 적용시킬수 있을까?

10개의 댓글

2018.04.16
...? 그걸 루트n 안에 찾는 알고리즘을 개발하면 너는 필즈상감임.
아니 필즈상이 아니라 수학 교과서에 영원히 이름이 실릴듯
테이블 만들어서 하드코딩으로 출력하면 출력부분까지 루트N 만들 수 있을꺼 같긴한데 이건 아니겠지....


근데 에라테스토너스 가 뭐임??? 검색해도 전혀 안 나온다.
2018.04.17
@ᅟᅟᅟᅟ ㅤㅤㅤ
'에라토스테네스의 체'라고 소수 찾는 알고리즘
@decltype
오오 ㄳㄳ

검색해도 이상한거만 나오고 번역기 돌려도 없는 단어란 식이여서 뭔가 했음
루트 이야기 나오는 거 보면 전체 검증을 루트C 이내로 하란 소리가 아니라 수학공식 이용해서 하나의 수에 대해 나눠보는 문제같은데 문제 원문을 봐야겠지만 아마 이 이야기가 맞을 거임.

C가 합성수면 C = A * B (A, B는 1보다 큰 자연수). 따라서 둘 중 하나는 루트C보다 작거나 같음.
따라서 모든 수 검증할 필요 없이 루트 C이내로만 나눠봐서 검증하면 됨.

즉 내부 하나의 수에 대해 검증하는 루프는 따로 있고 그 루프를 돌리는걸 루트C번 까지 하란 문제 같은데. 즉 이중루프 구조에서 외부 루프를 루트C 만큼만.

참고로 소수 알고리즘 다룰 때 에라토스테네스의 체 이야기하면서 항상 같이 나오는 거니 검색해보면 아마 같이 나올거임.
2018.04.17
@알파스트라이크
하나의 수에 대해 소수 테스트 하는 루프가 따로 있다고 해도 그 외부 루프를 루트C 만큼만 돌릴수 없을텐데...?

그게 가능하면 소수테스트 하는 루프 시간복잡도 루트N*외부 루프 루트N해서 O(N)안에 N이하의 소수를 판별하는 알고리즘이 완성되는데, 현존하는 어떤 알고리즘보다 빠름...
@decltype
내가 설명을 좀 헷갈리게 썼는데 니 이야기를 부정하는 게 아님ㅋㅋ 저 문제 자체가 모든 연산 자체를 루트N만큼 줄이란 게 아닐거라고. 소수 알고리즘 검색해 보면 뭔 소린지 알거임.
2018.04.17
@알파스트라이크
"즉 이중루프 구조에서 외부 루프를 루트C 만큼만."
여기서 내부 루프를 외부 루프로 잘못쓴거지?

내부루프가 primality test하는 루프아녀?
@decltype
잘못쓴건 아님. 어차피 이경우는 둘중 어느걸 외부루프로 두냐는 짜기 나름이라 별 상관없거든. 내가 헷갈리게 쓴게 문제라면 문제인데 ㅋㅋ
여튼 결론은
2부터 N-1까지 소수 구할 때 당연히 에라토스테네스의 체를 쓰잖아? 그 체를 쓰는 방식 자체가 2배수 모두 거르고 3배수 모두 거르고... 루트N까지 거르고 끝임. (루트N)+1부터는 이미 '걸러진 상태'기 때문에.

애초 저 문제 낸 양반이 알고리즘 쪽 강의하는 교수나 이런 사람이라면 이거 의도한거였을게 100퍼임.
2018.04.17
@알파스트라이크
가릿가릿
번호 제목 글쓴이 추천 수 날짜 조회 수
공지 컴퓨터 / IT에 관련된 글을 올려주시기 바랍니다. 21 overflow 4 2016.08.22 16059
73972 [후방주의] 4790k -> 8700k 갈아엎으려고하는데 조언 부탁합니다 9 6265255 1 2018.04.16 554
73971 중고로 노트북사기로햇는데 4 컴돌입벌레혐오 0 2018.04.16 142
C언어 소수 찾는 알고리즘 좀 봐줄래양? 10 빅뚝배기맨 0 2018.04.16 176
73969 구글검색 이미지보기가 이상하게 변했는데 6 김기복 1 2018.04.16 158
73968 메인보드 교체후 윈도우 설치 할려는데 안됨 ㅠㅠ 11 어휴쯔읏 0 2018.04.16 136
73967 c언어 구조체 점 봐주세여 6 뚝배기사냥꾼 0 2018.04.16 92
73966 좆크트에서 번호이동 하려하는데 도움점 3 병신을보면햝는개 0 2018.04.16 52
73965 갤8 쓰기속도 개손해보고 살았네;; 8 rosenrose 0 2018.04.16 407
73964 amd 2200g랑 2400g 궁금한거 있어욤 5 RUNASIMI 0 2018.04.16 261
73963 여기 앱 질문도 받아주나요 3 4edg587 0 2018.04.16 54
73962 자바 질문있쓥니당!!! 19 쏠탈플리즈 0 2018.04.16 72
73961 아수스 ai suite 아는 사람 있어? 4 카드 0 2018.04.16 210
73960 970 중고 요즘 구하는거 별로임? 4 ztarrc 0 2018.04.16 251
73959 8100 vs 2200g 노게임 기준 머가 더나음 4 총기탄약계원 0 2018.04.16 231
73958 그래픽카드 살려는데 6 크스크스 0 2018.04.16 194
73957 스크래치에서 왜 입력 요소에 2 교육행정직 0 2018.04.16 42
73956 컴알못 ) cpu만 업그레이드하려는데 지금사용하는 메인보드와... 8 8ㅅ8 8ㅅ8 0 2018.04.16 132
73955 이거 죽었다고 봐야하지? 3 meDSKK2 0 2018.04.16 234
73954 모알못인데 도와주라.. 10 영영쓰 0 2018.04.16 90
73953 유툽 영상올릴때 파일형식에 따라서 재생시 로딩길어지는게 ... 2 폐폐 0 2018.04.16 28
서버에 요청 중입니다. 잠시만 기다려 주십시오...