SHARE
TWEET

Untitled

a guest Sep 13th, 2017 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.Scanner;
  3.  
  4. public class Primenumber {
  5.  
  6.     public static void main(String[] args) throws IOException {
  7.         BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
  8.         Scanner sc = new Scanner(System.in);
  9.        
  10.         int t,m,n=0;
  11.         int r=0;
  12.        
  13.             t=Integer.parseInt(sc.next());
  14.             for(int i=1;i<=t;i++){
  15.                 m=Integer.parseInt(sc.next());
  16.                 n=Integer.parseInt(sc.next());
  17.                
  18.                 if(m==1||m==2) {
  19.                     System.out.println(2);
  20.                     m=3;
  21.                 }
  22.                
  23.                 if(m%2==0){
  24.                     r=m+1;
  25.                    
  26.                 }else {
  27.                     r=m;
  28.                 }
  29.                    
  30.                 for(;r<=n;r+=2){
  31.                     if(miller_rabin_final(r)==true)
  32.                         System.out.println(r);
  33.                 }
  34.                 System.out.println();
  35.             }
  36.         //  System.out.println();
  37.            
  38.        
  39.         }
  40.        
  41.        
  42.        
  43.        
  44.        
  45.        
  46.        
  47.    
  48.    
  49.     private static int[] modexp(int base, int power, int mod, int trailingzeros) {
  50.         int Profile[]=new int[32];
  51.         long result = 1;     
  52.         int Info[]=new int[2];
  53.         Info[1]=1;
  54.        
  55.        
  56.         for (int i = 31; i >= 0; i--) {
  57.             result = (result*result) % mod;
  58.        
  59.             if(i<trailingzeros){
  60.                 Profile[31-i]=(int)result;
  61.             }
  62.            
  63.            
  64.             if ((power & (1 << i)) != 0) {
  65.                 result = (result*base) % mod;
  66.             }
  67.         }
  68.        
  69.         //Test ob Profil regulär oder nicht
  70.         int test=Profile[0];
  71.         for(int i=1;i<trailingzeros;i++){
  72.         //"test" hängt immer einen Schritt hinter Profile hinterher. Falls
  73.         //Profile[i]=1 und Profile[i+1]!=-1,1 break und bool falsch zurückgeben.
  74.             if(test==1&&(Profile[i]!=-1&&Profile[i]!=1)){
  75.                 Info[1]=0;
  76.                 break;
  77.             }
  78.             test=Profile[i];
  79.         }
  80.        
  81.         Info[0]=(int)result;
  82.         return Info;
  83.        
  84.     }
  85.    
  86.     private static boolean miller_rabin_test(int a, int n) {
  87.         int d = n - 1;
  88.         int s = Integer.numberOfTrailingZeros(d);
  89.        
  90.         d >>= s;
  91.         int a_power[] = modexp(a, d, n, s);
  92.         if (a_power[1] == 1&&a_power[0]==1) return true;
  93.        
  94.        /* for (int i = 0; i < s-1; i++) {
  95.             if (a_power[] == n-1) return true;
  96.             a_power = modexp(a_power, 2, n,s);
  97.         }*/
  98.         //if (a_power[] == n-1) return true;
  99.         return false;
  100.     }
  101.    
  102.     public static boolean miller_rabin_final(int n) {
  103.         if (n <= 1) return false;
  104.         else if (n == 2) return true;
  105.         else if (miller_rabin_test( 2, n) &&
  106.             (n <= 7  || miller_rabin_test( 7, n)) &&
  107.             (n <= 61 || miller_rabin_test(61, n)))
  108.             return true;
  109.         else
  110.             return false;
  111.     }
  112.    
  113. }
RAW Paste Data
Top