C/C++ GMP ライブラリを使う（Java でいう BigInteger です)

とても大きな数を扱うとき、Java では BigInteger などを使うと制限なしです。しかも標準装備。

ここで扱いたい大きな数というのは、ほかでもないメルセンヌ素数です。とんでもなく大きな数となるのでどうしてもライブラリを使う必要があります。

ほかでもないというのは、メルセンヌ素数という形であれば素数であるかの判定が容易という理由から、発見された最大の素数はメルセンヌ素数であるからです。

	// Mersenne.java -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:56:11 2016
	// Keywords:
	// Commentary:
	// Compile as (does not require any additional library):
	// javac Mersenne.java
	//
	// Run as:
	// java Mersenne n
	// Code:
	import java.math.*;
	import java.io.*;
	public class Mersenne
	{
	public static BigInteger mersenne(int p)
	{
	return (BigInteger.ONE.shiftLeft(p)).subtract(BigInteger.ONE);
	}
	public static void main(String args[])
	{
	int n=1;
	try
	{
	if(args.length==0)
	{
	System.out.print("Enter a number: ");
	BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
	String str=reader.readLine();
	n=Integer.parseInt(str);
	}
	else
	{
	n=Integer.parseInt(args[0]);
	}
	BigInteger mp=mersenne(n);
	System.out.println(mp);
	}
	catch(Exception e){e.printStackTrace();}
	}
	}
	// Mersenne.java ends here

view raw Mersenne.java hosted with ❤ by GitHub

このプログラムをCで実装しようとすると、GMPなど外部ライブラリが必要となります。GMPを使ったソースです。

	// mersenne.cpp -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:53:34 2016
	// Keywords:
	// Commentary:
	//
	// Compile as (requires gmp library):
	// gcc mersenne.c -lgmp
	//
	// Code:
	#include <stdlib.h>
	#include <stdio.h>
	#include <unistd.h>
	#include <gmp.h>
	void mersenne(mpz_t r, int p)
	{
	mpz_ui_pow_ui(r,2,p);
	mpz_sub_ui(r,r,1);
	}
	int main(int argc, char* argv[])
	{
	int nopt=0;
	char *nparam=NULL;
	int opt;
	while((opt=getopt(argc, argv, "h"))!=-1) {
	switch(opt){
	case 'h':
	printf("Usage: mersenne n\n");
	break;
	}
	}
	int n;
	if(optind < argc)
	{
	n=atoi(argv[optind]);
	mpz_t t;
	mpz_init(t);
	mersenne(t,n);
	gmp_printf("%Zd \n",t);
	mpz_clear(t);
	}
	return 0;
	}
	// mersenne.cpp ends here

view raw mersenne.c hosted with ❤ by GitHub

このプログラムもC++を使うと分かりやすくなります。初期化、後始末などコンストラクタ、デストラクタで書けるからです。

	// mersenne.cpp -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:53:34 2016
	// Keywords:
	// Commentary:
	//
	// Compile as (requires gmp library):
	// g++ mersenne.cpp -lgmpxx -lgmp
	//
	// Code:
	#include <unistd.h>
	#include <gmpxx.h>
	#include <iostream>
	using namespace std;
	mpz_class mersenne(int p)
	{
	mpz_class mp;
	mpz_ui_pow_ui(mp.get_mpz_t(),2,p);
	mp--;
	return mp;
	}
	int main(int argc, char* argv[])
	{
	int nopt=0;
	char *nparam=NULL;
	int opt;
	while((opt=getopt(argc, argv, "h"))!=-1) {
	switch(opt){
	case 'h':
	printf("Usage: mersenne n\n");
	break;
	}
	}
	int n;
	if(optind < argc)
	{
	n=atoi(argv[optind]);
	mpz_class mp=mersenne(n);
	cout << mp;
	}
	return 0;
	}
	// mersenne.cpp ends here

view raw mersenne.cpp hosted with ❤ by GitHub

C#だとこんな感じでしょうか。

	// Mersenne.cs -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:53:34 2016
	// Keywords:
	// Commentary:
	//
	// Tested with VC++ 2015
	//
	// Code:
	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	using System.Numerics;
	namespace Prime
	{
	class Program
	{
	static BigInteger mersenne(int p)
	{
	BigInteger mp = 1;
	mp = (mp << p) - 1;
	return mp;
	}
	public static bool isPrime(BigInteger n)
	{
	bool isPrime = true;
	BigInteger max = n;
	BigInteger i = 1;
	while (i < max)
	{
	if (i != 1 && (n % i) == 0)
	{
	isPrime = false;
	break;
	}
	max = n / i;
	i++;
	}
	return isPrime;
	}
	static void Main(string[] args)
	{
	int[] p = { 2, 3, 5, 7, 13, 17, 19, 31 };
	for(int i=0;i<p.Length;i++)
	{
	BigInteger mp=mersenne(p[i]);
	if (isPrime(mp))
	Console.WriteLine(mp + " is a prime");
	else
	Console.WriteLine(mp + " is not a prime");
	}
	}
	}
	}
	// Mersenne.cs ends here

view raw Mersenne.cs hosted with ❤ by GitHub