코세 버전 is_prime


(codesafer) #1
template< typename T >
inline  bool    is_prime( T n )
{
    if( n < 7 )
    {
        if( n < 2 || n == 4 || n == 6 )
            return  false;
    }
    else
        if( n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n < 7 )
            return  false;

    for( T i = 7; i * i <= n; i += 30 )
        if( n % ( i      ) == 0 ||
            n % ( i +  4 ) == 0 ||
            n % ( i +  6 ) == 0 ||
            n % ( i + 10 ) == 0 ||
            n % ( i + 12 ) == 0 ||
            n % ( i + 16 ) == 0 ||
            n % ( i + 22 ) == 0 ||
            n % ( i + 24 ) == 0 )
            return  false;

    return  true;
}

2를 제외하면 소수는 홀수에서만 등장하는건 익히 아실테고,
7 미만의 소수를 제외하면
30 개의 주기로 여덟군데 만 소수가 발생할 확률이 존재한다는 특성을 활용한 코드입니다.


(ㄴㅂㄷㄱㄷㄱ) #2

Wa


(codesafer) #3
[ 1]  [13]    25  [37]  [49]

     2    14    26    38    50

 51     3    15    27    39

    52     4    16    28    40

[41]  [53]    5   [17]  [29]

    42    54     6    18    30

[31]  [43]   55   [ 7]  [19]

    32    44    56     8    20

 21    33    45    57     9

    22    34    46    58    10

[11]  [23]   35   [47]  [59]

    12    24    36    48    60

제가 발견한( 딴 사람들도 발견했겠지? ) 소수 후보의 위치입니다.
( 예외 : 7 미만의 소수 )
10 * 12 에 우하향 증가 수 입니다. ( 우측이나 아래 경계로 빠져 나가면 좌측과 위에서 들어옴 )
이렇게 놓으면 완전히 대칭적이죠.


(Deneb) #4

찾아보니 관련 정리가 있더군요. [1] 증명은 찾기 어려워서 직접 증명해보았습니다.

주장 1. 임의의 정수 m, n 에 대하여 r = 30m + 7 일 때, r, r + 4, r + 6, r + 10, r + 12, r + 16, r + 22, r + 2430n \pm 1, 7, 11, 13 으로 나타낼 수 있다.

정리 1. 임의의 정수 k 에 대하여, n \ge 730k \pm 1, 7, 11, 13 이 아니면 n 은 소수가 아니다.

증명) 각각의 경우로 나누어 생각해보자. n = 30k \pm l 의 형태로 쓸 때 0 \le l \le 15 인 경우만 조사하면 된다.

  • n = 30k \pm 0, 2, 4, 6, 8, 10, 12, 14 은 2로 나누어 떨어지므로 소수가 아니다.
  • n = 30k \pm 3, 9, 15 은 3으로 나누어 떨어지므로 소수가 아니다.
  • n = 30k \pm 5 은 5로 나누어 떨어지므로 소수가 아니다.

이상으로 남은 경우는 n = 30k \pm 1, 7, 11, 13 뿐이다. 이는 소수의 필요조건이다. \square

정리 2. 임의의 정수 k 에 대하여, n \ge 730k \pm 1, 7, 11, 13 이면 n 은 소수다. (다시말해, 정리 1의 역도 참이다.)

증명) 이건 다른 분께 패스… ㅠㅠ

참고 자료
[1] Primes coprime to 30 - OeisWiki


(codesafer) #5

응 누가 풀어놨넹.

잘 찾아냈음~

그리고 잘 정리했음.

근데 기하공간상 직교축의 대칭구조를 만든건 아니니 그건 내가 좀 유니크 할 듯 ㅋㄷㅋㄷ


(바보털) #6

증명 2 반례) 91 = 30 * 3 + 1 = 7 * 13


(바보털) #7

베주 항등식 생각해 보면 반례 무한히 많을듯…?


(sh) #8

도입부에 if else 어색한건 나뿐인가요


(codesafer) #9

뭐가요?


(codesafer) #10

‘소수’ 의 후보다. 라고 하면 되는데 ‘소수다’ 라고 해서 틀린 정리.

  • 알고 적었을테지만.

(바보털) #11

생각해보니까 베주까지 갈필요 없이 (30a + 1)(30b + 1)도 30(30ab + a + b) + 1이고 나머지도 비슷하게 가능하넵…

어색한건 else if 이렇게 써도 되는걸 굳이 줄 바꿔서 쓴걸 말하는 듯 합니다


(ㄴㅂㄷㄱㄷㄱ) #12

아마 sh 님은

if (n < 7)
...
else if ( ... || n < 7) 

말씀하신 거 아닐까요?
왠지 있는게 가독성이 더 좋다고 생각하는 1인


(sh) #13

ㅇㅇ 그리고 내가 아는 ㅋㅅ님아는 저정도 ㄴ
레인지는 걍 테이블같은거로 발랏을거같은데…
@codesafer 누구냐너 !


(codesafer) #14

아 테이블 바를껄.


(codesafer) #15

근데 꼴랑 저거 가지고 테이블 발라봐야 자주 들어온다는 보장이 없으면
캐시만 깨먹지뭐.

template< typename T >
inline  bool    is_prime( T n )
{
    if( n < 7 )
    {
        constexpr   bool    primes[]
        {
            false, false, true, true, false, true, false,
        };
        return  primes[ n ];
    }

    if( n % 2 == 0 || n % 3 == 0 || n % 5 == 0 )
        return  false;

    for( T i = 7; i * i <= n; i += 30 )
    {
        if( n % ( i      ) == 0 ||
            n % ( i +  4 ) == 0 ||
            n % ( i +  6 ) == 0 ||
            n % ( i + 10 ) == 0 ||
            n % ( i + 12 ) == 0 ||
            n % ( i + 16 ) == 0 ||
            n % ( i + 22 ) == 0 ||
            n % ( i + 24 ) == 0 )
            return  false;
    }
    return  true;
}

그래도 조건 하나 줄어드니까 해드렸음.


(codesafer) #16

오랜만에 수다를 엄청 떨었더니

졸려서 죽어버릴것 같…


(codesafer) #17

원래 초기 의도가 ( 이거 몇 달 전에 짠건데 )

  1. 나 답잖지만 음수 주면 그냥 false 얌전히 뱉아줄까?

  2. 메모리 종속성 없이 연산자 단순한 함수로 만들까?

요거 두 가지 였음.

쓰기 나름이긴 한데 음수 방어를 해버리면 조건 하나가 느는지라
조건 하나랑 메모리 종속성 중에 잇점이 있을까? 라고 생각하면
최신 컴파일러들은 몇 개의 constexpr 에 대해 메모리 리터럴 레벨이 아닌
코드 분기 레벨로 최적화 될 수도 있을꺼라 생각했음.
그렇게 생각하면 다양한 용도와 환경에서 굳이 성능이 들쭉날쭉해질 메모리를 안건드리는게
광범위한 사용에 적합해 보였지~

그러니까 첫번째 조건 ( < 7 ) 로 대부분 걸러질텐데 긍정적으로 봐도 이익이 너무 작다는거.


(codesafer) #18

다시 찬찬히 보니 ㄴㅂㄷㄱㄷㄱ 말이 맞네 ㅋㄷㅋㄷ

n < 7 저거 왜 else 에 있지.


(codesafer) #19

쪽팔리니까 이렇게 수습하자.

template< typename T >
inline  bool    is_prime( T n )
{
    if( n < 7 )
        return  ( n == 2 || n == 3 || n == 5 );

    if( n % 2 == 0 || n % 3 == 0 || n % 5 == 0 )
        return  false;

    for( T i = 7; i * i <= n; i += 30 )
        if( n % ( i      ) == 0 ||
            n % ( i +  4 ) == 0 ||
            n % ( i +  6 ) == 0 ||
            n % ( i + 10 ) == 0 ||
            n % ( i + 12 ) == 0 ||
            n % ( i + 16 ) == 0 ||
            n % ( i + 22 ) == 0 ||
            n % ( i + 24 ) == 0 )
            return  false;

    return  true;
}

(sloth) #20

prime day 때문에 이거 제목 보고도 움찔했었읍니다;;