C 소수판단 알고리즘

from Programming/algorithm 2008/08/02 14:53

오랜만에 글 써보네요.
미안하지만 오늘 글은 모두 아는 소수 판단 알고리즘입니다. ㅈㅅㅈㅅㅈㅅ

소수 : 1과 자신 외에는 나누어 떨어지는 정수가 없는 양의 정수.

소수의 정의만 보면 2부터 n-1까지 나누어보아서 나누어지지 않으면 소수 나누어지면 소수가 아니라고 할 수 있습니다.



이 함수는 느리다. ㅡ,.ㅡ
소수를 판별할 때 n의 제곱근까지만 나누어 보면 된다고 한다.

16을 보면 16의 약수는 1*16, 2*8, 3*6, 4*4, 6*3, 8*2, 16*2 이렇게 앞 뒤가 서로 대칭된다.
그래서 제곱근을 구해주는 합수 sqrt(int)함수를 써보겠습니다.



 소수를 구하는 다른 알고리즘에는 에라토스의 체가 있습니다.
1부터 n까지의 소수를 구한다고 할 때 소수의 배수를 지워나가면서 남아있는 수를 구하는 알고리즘입니다.


다음부턴 열심히 쓸게요. 때리지 마요 제발

이 글이 유익하다면 (굽신굽신) ->
Tag // , , , ,
Trackback(1) : Comment(4)

Trackback Address >> http://zfanta.com/trackback/397 관련글 쓰기

  1. Subject: 에라토스테네스의 체가 과연 빠르긴 빠르네

    Tracked from BLUEnLIVE's ZocKrWorld 2009/09/06 03:57  delete

    꼭 이런 짓을 하고싶을 때가 있다. 소수의 합을 구할 때 에라토스테네스의 체가 빠르다는 거 당연한데, 굳이 일일이 계산하는 거랑 비교해보고 싶었다. 왜 그런지 따윈 없고... 단지 있다면 얼마 전 모 블로그에 내가 쓴 답글이 신경쓰여서랄까나... 그래서 VS 2003.Net으로 만들어봤다. #include "stdafx.h" #include <memory.h> #include <math.h> #include <windows.h> #define PRI..

  1. Favicon of http://bluenlive.net BlogIcon bluenlive 2008/08/16 02:56  address  modify / delete  reply

    참고로, sqrt(n)까지 루프를 돌릴 때 홀수만 돌리면 됩니다.
    짝수는 어짜피 2x홀수이니까요.

    오랜만에 보니 반갑네요.

  2. Favicon of http://dizies2.tistory.com BlogIcon dizies 2008/09/10 19:11  address  modify / delete  reply

    아리스토테네스의 체에서 소수 i를 찾아서 i의 배수를 지울때 2i 부터 돌리는데 사실 i*i부터 돌려도 됩니다. 왜 그런지는 직접 해보시면..;;