[c언어] 메르센소수

 

메르센 소수를 출력하는 프로그램을 작성한다.

* 메르센 소수란?

2n-1꼴의 수를 메르센 수라고 하며, 메르센 수가 소수일 때 그 수를 메르센 소수라고 한다.

 

#include <stdio.h>
long long isMersenne(int n)
{
    int i;
    long long result = 1;

    for (i = 1;i <= n;i++)
        result *= 2;

    return result;
}

int isPrime(long long x)
{
    long long i;

    for (i = 2;i <= x - 1;i++)
        if (x % i == 0)
            return 0;

    return 1;
}

int main(void)
{
    long long num, i, value;

    printf("Enter a number: ");
    scanf("%lld", &num);

    for (i = 2;i <= num;i++)
    {
        value = isMersenne(i) - 1;

        if (isPrime(value) == 1)
            printf("(2 ^ %lld - 1) = %lld은 메르센 소수이다.\n", i, value);
    }
}

 

결과