날개넷

wingnet88.egloos.com

포토로그



[c언어] 소수구하기 소스. c언어소스

calc_prime :: O(n^2)
calc_prime2 :: O(n^2 / log n)
밑에껄로 돌리는게 미약하나마 더빠릅니다.
저질수준이니까 별 도움안될꺼에요...
부연설명 ---
 헬로날개넷 (2012-06-24 22:33:34)   추천:0 / 반대:0               IP:180.134.***.218      
아... 어차피 저 위의소수는 시간복잡도가 너무 높아 볼필요가 없어서 주석을 하나도 안달았어요;;; 그냥.. O(n log n)? 이정도로라도 시간복잡도를 줄일수있는방법이 있나해서,,,, ㅋㅋㅋㅋㅋㅋ O(n)이면 더 좋을텐데.. 이건 안될꺼같은데
 헬로날개넷 (2012-06-24 22:34:57)   추천:0 / 반대:0               IP:180.134.***.218      
그냥 구조체 내에 1~n 까지 숫자를 저장하고, flag 하나 두어서, 만약 나눠지는 숫자면 flag 를 1로 바꾸는식으로 구현했어요.. 첫번째꺼는 정말 고전식으로 만약 10이 소수인지 아닌지 알아보려면 1~9까지 전부다 나눠보는 방식이고, 두번째꺼는 조금더 나아져서, 10이 소수인지 아닌지 알아보려면 10보다 작은 소수인 2,3,5,7 을 이용해서 나눠보는 방식으로 구현했어요...
 헬로날개넷 (2012-06-24 22:36:09)   추천:0 / 반대:0               IP:180.134.***.218      
댓글수정이 안되네;;; 첫번째껀 n까지의 숫자를 n-1번 나눠보니까 O(n^2)이고 두번째껀 n까지의 숫자를 n보다 작은 소수의 개수만큼 나눠보니까 O(n^2 / log n)이 나온거구요... (n보다 작은 소수의 개수는 n / log n )

덧글

댓글 입력 영역