글 읽기 - 밀러 라빈 처음 사용해보려고 하는데 어느 부분이 잘못된지 알려주실수 있으신가요?

onseokjun 2년 전 0

아래 코드 대로 해서 for문으로 돌려가면서 1부터 소수 개수 새어봤을땐 1부터 10000까지는1229개로 정상적으로 나오지만,

100000으로 늘어났을때 9552개여야 하는데 9592개로 합성수 40개가 더 세지는것 같습니다

그런데 몇번째 고쳐보고 여러군데 찾아봐도 어디가 틀린건지 문제점을 모르겠어서 질문 드립니다

문제 조건이 int 범위라 일부러 오버 안되게 long long으로 했는데도 안되네요..

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long prime[14] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};

long long modpower(long long a, long long b, long long mod){
    if(b == 0){
        return 1;
    }
    a %= mod;
    if(b == 1){
        return a;
    }

    long long ret = 1;
    while(b > 0){
        if(b % 2 == 1){
            ret = (ret * a) % mod;
        }
        a = (a * a) % mod;
        b /= 2;
    }

    return ret;
}

int composite(long long a, long long input, long long d, int r){
    if(input % a == 0){
        return 1;
    }
    long long temp = modpower(a, d, input);
    if(temp == 1 || temp == input - 1){
        return 0;
    }
    for(int i = 1; i < r; i++){
        temp = (temp * temp) % input;
        if(temp == input - 1){
            return 0;
        }
    }
    return 1;
}

int Miller_Rabin(long long input){
    if(input == 1){
        return 0;
    }
    long long d = input - 1;
    int r = 0;

    while(d % 2 == 0){
        d /= 2;
        r ++;
    }

    for(int i = 0; i < 13; i++){
        if(input == prime[i]){
            return 1;
        }
        if(composite(prime[i], input, d, r)){
            return 0;
        }
    }
    return 1;
}

int main() {
    int test;
    scanf("%d", &test);
    int ans = 0;

    while(test --){
        long long N;
        scanf("%lld", &N);
        
        N = 2 * N + 1;
        if(Miller_Rabin(N) == 1){
            ans ++;
        }
    }
    printf("%d", ans);
	return 0;
}

onseokjun 2년 전 0

1부터 10만까지의 소수는 9592개가 맞네요 인터넷 자료가 잘못 나와있네요

그리고 넓이가 2^32가까이 있으니 long long 이 아니라 unsigned long long 으로 해줘야 맞게 나오는군요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

밀러 라빈 처음 사용해보려고 하는데 어느 부분이 잘못된지 알려주실수 있으신가요?

onseokjun 2년 전 0

onseokjun 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말