読者です 読者をやめる 読者になる 読者になる

クロビーボ

私的忘備録

双子素数を求めるプログラム

整数論において次の未解決問題があります。

問題
 双子素数は無限個存在するか?


ここで、正の整数 {n} に対して、{n}{n+2} がともに素数であるとき、ペア {(n, n+2)} を双子素数と呼びます。


例えば、 {(3, 5)}{(5, 7)}{(11, 13)} は双子素数です。



今回の記事では、ある正の整数以下の双子素数たちを求めるJavaプログラムを紹介します。

方法としては、まずある正の整数以下の素数たちをエラトステネスの篩を用いて求め、その後に、双子素数の条件を満たすものをfor文を用いて列挙することを考えました(より効率の良い方法があれば教えていただけるとありがたいです)。

というわけで、エラトステネスの篩を思い出しましょう。


命題(エラトステネスの篩)
 整数 {n>1}合成数ならば、{\sqrt{n}} 以下の素数の約数を持つ。


この命題の対偶を取る事により

 整数 {n>1}{\sqrt{n}} 以下の素数の約数を持たないならば、{n}素数である

ことが従います。

(この命題の証明は参考文献に挙げた本等を参照してください。)


ですので、これを用いてある正の整数以下の素数たちのリストを次のように構成しましょう。

static ArrayList<Integer> prime_set(int n) {
    ArrayList<Integer> prime_set = new ArrayList<Integer>();
    for (int i = 2; i < n; i++) {
        boolean hantei = true;
	for (int j = 2; j*j <= i; j++) {
	    if(i % j == 0) {               //約数が存在するかチェック
	        hantei = false;    
		break;
	    }
	}
	if(hantei) {            //素数である場合はリストに追加
	    prime_set.add(i);
	}
    }
    return prime_set;	
}


次に、このようにして作った素数たちのリストを用いて、双子素数を求めそれらを表示するメソッドを次のように構成します。

static void show_twin(ArrayList<Integer> a) {
    for (int i = 0; i < a.size() - 1; i++) {
        if((a.get(i)+2) == a.get(i+1)) {
	    System.out.println("("+a.get(i)+", "+a.get(i+1)+")");
	}
    }
}

このプログラムでは、双子素数の定義をそのままプログラムに書き直したものになっています。

さて、これらを用いて、以下のようなユーザーが入力した整数値以下の双子素数を求めるプログラムを作ることができます:

import java.util.*;

public class twin_primes {
	
    static Scanner sc = new Scanner(System.in);
	
    public static void main(String[] args) {
        int n = 0;
	do {
	    System.out.println("Please enter a positive integer: ");
	    n = sc.nextInt();
	} while (n <= 0);
		
	ArrayList<Integer> primse = prime_set(n);
		
	System.out.println("We have twin primes less than 10000 as follows:");
	show_twin(primes);

	}
	static ArrayList<Integer> prime_set(int n) {
	    ArrayList<Integer> prime_set = new ArrayList<Integer>();
	    for (int i = 2; i < n; i++) {
	        boolean hantei = true;
	        for (int j = 2; j*j <= i; j++) {
	            if(i % j == 0) {       
		        hantei = false;
		        break;
	            }
	        }
	        if(hantei) {
	            prime_set.add(i);
	        }
	    }
	    return prime_set;
	}

	static void show_twin(ArrayList<Integer> a) {
	    for (int i = 0; i < a.size() - 1; i++) {
	        if((a.get(i)+2) == a.get(i+1)) {
	            System.out.println("("+a.get(i)+", "+a.get(i+1)+")");
		}
	    }
	}
}

次の入力

1000

に対して、次の出力が得られます。

We have twin primes less than 10000 as follows:
(3, 5)
(5, 7)
(11, 13)
(17, 19)
(29, 31)
(41, 43)
(59, 61)
(71, 73)
(101, 103)
(107, 109)
(137, 139)
(149, 151)
(179, 181)
(191, 193)
(197, 199)
(227, 229)
(239, 241)
(269, 271)
(281, 283)
(311, 313)
(347, 349)
(419, 421)
(431, 433)
(461, 463)
(521, 523)
(569, 571)
(599, 601)
(617, 619)
(641, 643)
(659, 661)
(809, 811)
(821, 823)
(827, 829)
(857, 859)
(881, 883)


参考文献

整数論1: 初等整数論からp進数へ

整数論1: 初等整数論からp進数へ