seek Prime Number.

Prime.java

/**********************************************************************
Date: 2014-04-14
Author: Leonardone @ NEETSDKASU

★素数探索

素数探索のアルゴリズムを思いついたのでここに記す。

※自分で思いついたが、凡人の俺が思いつくくらいなので
※既に名のある有名なアルゴリズム、あるいはその劣化バージョンにだと思われる
※ググってないのでこのアルゴリズムの名前とかは分からない

●アルゴリズム概要

見つかった素数とそれ以下の素数の倍数でない数を導出する式(kn+d)を使い次の素数を求める


●アルゴリズム説明

2は素数なので
 2n+0  (2の倍数)
 2n+1  (2の倍数でない)
[n=0,1,2,3, ...]
と正数全体を分けられる
従って 2 の次にくる素数は 2の倍数でない式
 2n+1 
の1つの式で 2より大きい数の中で最小の数 である
ここで n=0 において 2より大きい数の中で最小の数 である 3 が見つかり 3 は素数である
ここで 2の倍数でない式 2n+1 は
 2(3n+0) + 1 = 6n + 1  (3の倍数でない)
 2(3n+1) + 1 = 6n + 3  (3の倍数)
 2(3n+2) + 1 = 6n + 5  (3の倍数でない)
[n=0,1,2,3, ...]
と書ける
従って 3 の次に来る素数は 3の倍数でない式
 6n+1, 6n+5 
の2つ式で 3より大きい数の中で最小の数 である
ここで n=0 において 3より大きい数の中で最小の数 である 5 が見つかり 5 は素数である
ここで 3の倍数でない式 6n+1 と 6n+5 は
 6(5n+0) + 1 = 30n +  1  (5の倍数でない)
 6(5n+1) + 1 = 30n +  7  (5の倍数でない)
 6(5n+2) + 1 = 30n + 13  (5の倍数でない)
 6(5n+3) + 1 = 30n + 19  (5の倍数でない)
 6(5n+4) + 1 = 30n + 25  (5の倍数)
 6(5n+0) + 5 = 30n +  5  (5の倍数)
 6(5n+1) + 5 = 30n + 11  (5の倍数でない)
 6(5n+2) + 5 = 30n + 17  (5の倍数でない)
 6(5n+3) + 5 = 30n + 23  (5の倍数でない)
 6(5n+4) + 5 = 30n + 29  (5の倍数でない)
[n=0,1,2,3, ...]
と書ける
従って 5 の次に来る素数は 5の倍数でない式
 30n+1, 30n+7, 30n+13, 30n+19, 30n+11, 30n+17, 30n+23, 30+29
の8つの式で 5より大きい数の中で最小の数 である
ここで n=0 において 5より大きい数の中で最小の数 である 7 が見つかり 7 は素数である
ここで先ほどと同様に 5の倍数でない式を
 30n(7n+0) +  1 = 210n +   1  (7の倍数でない)
 30n(7n+1) +  1 = 210n +  31  (7の倍数でない)
 30n(7n+2) +  1 = 210n +  61  (7の倍数でない)
 30n(7n+3) +  1 = 210n +  91  (7の倍数)
 30n(7n+4) +  1 = 210n + 121  (7の倍数でない)
 30n(7n+5) +  1 = 210n + 151  (7の倍数でない)
 30n(7n+6) +  1 = 210n + 181  (7の倍数でない)
 30n(7n+0) +  7 = 210n +   7  (7の倍数)
 30n(7n+1) +  7 = 210n +  37  (7の倍数でない)
 30n(7n+2) +  7 = 210n +  67  (7の倍数でない)
 30n(7n+3) +  7 = 210n +  97  (7の倍数でない)
(中略)
 30n(7n+5) + 29 = 210n + 179  (7の倍数でない)
 30n(7n+6) + 29 = 210n + 209  (7の倍数でない)
[n=0,1,2,3, ...]
と書ける
従って 7 の次に来る素数は 7の倍数でない式 で 7より大きい数の中で最小の数 である

同様の繰り返しで素数を探索できる


●備考

・このアルゴリズムの問題点は式の保持にメモリが大量に必要になることである

・素数探索の式 kn+d はそれまでの素数の倍数を含まない数を導き出す式であり
　素数探索の式 kn+d において素数であることが保障されるのは最後に見つかった素数より大きい数で最小の数のみである

・素数探索の式 kn+d において n=0 のときの値、すなわち d が一見すると素数のように見えるが
　今後見つかる素数の倍数である可能性があるためそれらが素数であるかどうかは分からない
　※俺は数学に明るくないのでこの部分が正しいかどうかは分からない分からない


**********************************************************************/

// Javaによる実装例
//
// Prime.java
//
package myapp.number;

import java.lang.*;
import java.util.Arrays;

public class Prime
{
	public static void main(String[] args) throws java.lang.Exception
	{
		long[] d = {0L}; // 素数探索式 kn+d の d の部分
		int len = 1; // 素数探索式 kn+d の数
		long k = 1L; // 素数探索式 kn+d の k の部分
		long prime = 1L; // 最後に見つかった素数
		long mind = 1L; // 探索を少なくする工夫
		
		for (int c = 0; c < 20; c++) // 20ループくらいでそれなりの数が求まるんじゃないかと
		{
			// 素数探索
			long nextprime = 0L;
			for (int n = 0; n < 10; n++) // n < 10 は適当な数字
			{
				if (nextprime > 0L && nextprime < k * (long)n + mind)
				{
					break;
				}
				for (int i = 0; i < len; i++)
				{
					long tmp = k * (long)n + d[i]; // kn + d
					if (tmp > prime)
					{
						if (nextprime == 0L)
						{
							nextprime = tmp;
						}
						else if (tmp < nextprime)
						{
							nextprime = tmp; // 前回見つかった素数より大きい数で最小の数
						}
					}
				}
			}
			prime = nextprime;
			System.out.print(" " + prime + ",");
			
			// 次の探索の準備
			long size = prime * (long)len;
			if ((size * (long)(Long.SIZE / 8)) >= Runtime.getRuntime().freeMemory())
			{
				// メモリ不足なので次の探索式を求められない
				break;
			}
			long[] temp = new long[(int)size];
			int templen = 0;
			mind = 0L;
			for (int j = 0; j < prime; j++)
			{
				for (int i = 0; i < len; i++)
				{
					long nextd = k * j + d[i]; // k(k'n + d') + d の kd' + d の部分
					if (nextd % prime != 0L)
					{
						temp[templen] = nextd; // primeの倍数でない場合のみ採用
						templen++;
						if (mind == 0)
						{
							mind = nextd;
						}
						else if (nextd < mind)
						{
							mind = nextd;
						}
					}
				}
			}
			k *= prime; // k(k'n + d') + d の kk' の部分、新しい式 kn+d の k
			d = temp;  // d の更新、新しい式 kn+d の d
			len = templen; // 新しい式 kn+d の数
		}
		System.out.println();
	}
}

Prime3.java

/* https://gist.github.com/neetsdkasu/10652417 の
 * Prime.javaでの素数探索アルゴリズムで素数を求めてみた結果
 * 俺のアイデアは糞なくらい遅いアルゴリズムだった
 * これは全く使えない！！
 *
 * 下記コードの実行結果
 * correct
 * Sieve of Eratosthenes's time: 7
 * My idea's time: 1588
 */
package myapp.number;

public class Prime3
{
	public static void main(String[] args)
	{
		long time = System.currentTimeMillis();
		Prime3 p = new Prime3();
		
		while (p.calcMin() && p.next())
		{
		}
		
		p.calc();
		time = System.currentTimeMillis() - time;
		
		//p.print();
		
		p.test();
		System.out.println("My idea's time: " + time);
	}
	
	int limit = 80000;
	int k = 2;
	int b = 2;
	int[] d = new int[]{ 1 };
	int dc = 1;
	int min = limit;
	int[] p = new int[limit];
	int pc = 0;
	
	Prime3()
	{
		p[pc] = 2;
		pc++;
	}
	
	boolean calcMin()
	{
		min = limit;
		for (int n = 0; k * n + d[0] <= min; n++) {
			for (int i = 0; i < dc; i++) {
				int t = k * n + d[i];
				if (t <= b) {
					continue;
				}
				if (t < min) {
					min = t;
				}
			}
		}
		return min != limit;
	}
	
	boolean next()
	{
		int[] td = new int[limit];
		int tdc = 0;
		for (int i = 0; i < dc; i++) {
			for (int j = 0; j < min; j++) {
				int t = k * j + d[i];
				if (t < limit) {
					if (t % min != 0) {
						td[tdc] = t;
						tdc++;
					}
				} else {
					break;
				}
			}
		}
		d = td;
		dc = tdc;
		k *= min;
		b = min;
		p[pc] = min;
		pc++;
		return k < limit;
	}
	
	void calc()
	{
		java.util.Arrays.sort(d, 0, dc);
		int tdc = dc;
		int s = 0;
		while (tdc > 0) {
			while (d[s] <= min) {
				s++;
				if (s >= tdc) {
					return;
				}
			}
			int n = s;
			min = d[s];
			p[pc] = min;
			pc++;
			for (int j = s + 1; j < tdc; j++) {
				if (d[j] % min != 0) {
					d[n] = d[j];
					n++;
				}
			}
			tdc = n;
		}
		
	}
	
	void print()
	{
		for (int i = 0; i < pc; i++) {
			System.out.print(p[i] + " ");
		}
		System.out.println();
	}
	
	void test()
	{
		int[] t = new int[limit];
		long time = System.currentTimeMillis();
		for (int i = 2; i < limit; i++) {
			if (t[i] == 0) {
				for (int j = i * 2; j < limit; j += i) {
					t[j] = 1;
				}
			}
		}
		time = System.currentTimeMillis() - time;
		int n = 0;
		for (int i = 2; i < limit; i++) {
			if (t[i] == 0) {
				if (p[n] != i) {
					System.out.println("Not Prime: " + p[n] + " (Next Right Prime: " + i + ")");
					return;
				}
				n++;
			}
		}
		System.out.println("correct");
		System.out.println("Sieve of Eratosthenes's time: " + time);
	}
}