fork download
copy 
  1. // 変な数字は考慮しない
  2.  
  3. class PrimeMT{
  4.     public int num;
  5.     public boolean[] primeData;
  6.     public boolean[] primeDataSolved;
  7.  
  8.     public PrimeMT(int n){
  9.         num=n;
  10.         initialize();
  11.         solve();
  12.         for (int i=-8;i<=8;i++)
  13.             System.out.println("isPrime("+(num/2+i)+") -> "+isPrime(num/2+i));
  14.     }
  15.  
  16.     public static void main(String[] args){
  17.         new PrimeMT(1000100);
  18.     }
  19.  
  20.     public void initialize(){
  21.         primeData = new boolean[num];       // 全てfalse
  22.         primeDataSolved = new boolean[num]; // 全てfalse
  23.         primeData[0]=false; // ?
  24.         primeData[1]=false;
  25.         primeData[2]=true;
  26.     }
  27.  
  28.     public void solve(){
  29.         Thread t1=new SolveThread(this);
  30.         Thread t2=new SolveThread(this);
  31.         Thread t3=new SolveThread(this);
  32.         Thread t4=new SolveThread(this);
  33.         try{
  34.             t1.start();t2.start();t3.start();t4.start();
  35.             t1.join();t2.join();t3.join();t4.join();
  36.         }catch (InterruptedException e){
  37.             e.printStackTrace();
  38.         }
  39.     }
  40.  
  41.     public boolean isPrime(int i){
  42.         if (i<0 || num<=i) return false;
  43.         return primeData[i];
  44.     }
  45.  
  46.     public synchronized int getNext(int offset){
  47.         for (;offset<num;offset++)
  48.             if (!primeDataSolved[offset]){
  49.                 primeDataSolved[offset]=true;
  50.                 return offset;
  51.             }
  52.         return -1;
  53.     }
  54. }
  55.  
  56. class SolveThread extends Thread{
  57.     PrimeMT prime;
  58.     int current;
  59.     int num;
  60.     public SolveThread(PrimeMT p){
  61.         super();
  62.         prime=p;
  63.         num=p.num;
  64.         current=3;
  65.     }
  66.     public void run(){
  67.         while ((current=prime.getNext(current))!=-1){
  68.             int j;
  69.             for (j=2;j*j<current;j++)
  70.                 if (current%j==0) break;
  71.             if (current%j!=0){
  72.                 prime.primeData[current]=true;
  73.                 for (j=1;j*current<num;j++)
  74.                     prime.primeDataSolved[j*current]=true;
  75.             }
  76.         }
  77.     }
  78. }
Success #stdin #stdout 1.3s 321856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
isPrime(500042) -> false
isPrime(500043) -> false
isPrime(500044) -> false
isPrime(500045) -> false
isPrime(500046) -> false
isPrime(500047) -> false
isPrime(500048) -> false
isPrime(500049) -> false
isPrime(500050) -> false
isPrime(500051) -> false
isPrime(500052) -> false
isPrime(500053) -> false
isPrime(500054) -> false
isPrime(500055) -> false
isPrime(500056) -> false
isPrime(500057) -> true
isPrime(500058) -> false
https://ideone.com/kB8lYz
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!