Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.Scanner;
- public class Primenumber {
- public static void main(String[] args) throws IOException {
- BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
- Scanner sc = new Scanner(System.in);
- int t,m,n=0;
- int r=0;
- t=Integer.parseInt(sc.next());
- for(int i=1;i<=t;i++){
- m=Integer.parseInt(sc.next());
- n=Integer.parseInt(sc.next());
- if(m==1||m==2) {
- System.out.println(2);
- m=3;
- }
- if(m%2==0){
- r=m+1;
- }else {
- r=m;
- }
- for(;r<=n;r+=2){
- if(miller_rabin_final(r)==true)
- System.out.println(r);
- }
- System.out.println();
- }
- // System.out.println();
- }
- private static int[] modexp(int base, int power, int mod, int trailingzeros) {
- int Profile[]=new int[32];
- long result = 1;
- int Info[]=new int[2];
- Info[1]=1;
- for (int i = 31; i >= 0; i--) {
- result = (result*result) % mod;
- if(i<trailingzeros){
- Profile[31-i]=(int)result;
- }
- if ((power & (1 << i)) != 0) {
- result = (result*base) % mod;
- }
- }
- //Test ob Profil regulär oder nicht
- int test=Profile[0];
- for(int i=1;i<trailingzeros;i++){
- //"test" hängt immer einen Schritt hinter Profile hinterher. Falls
- //Profile[i]=1 und Profile[i+1]!=-1,1 break und bool falsch zurückgeben.
- if(test==1&&(Profile[i]!=-1&&Profile[i]!=1)){
- Info[1]=0;
- break;
- }
- test=Profile[i];
- }
- Info[0]=(int)result;
- return Info;
- }
- private static boolean miller_rabin_test(int a, int n) {
- int d = n - 1;
- int s = Integer.numberOfTrailingZeros(d);
- d >>= s;
- int a_power[] = modexp(a, d, n, s);
- if (a_power[1] == 1&&a_power[0]==1) return true;
- /* for (int i = 0; i < s-1; i++) {
- if (a_power[] == n-1) return true;
- a_power = modexp(a_power, 2, n,s);
- }*/
- //if (a_power[] == n-1) return true;
- return false;
- }
- public static boolean miller_rabin_final(int n) {
- if (n <= 1) return false;
- else if (n == 2) return true;
- else if (miller_rabin_test( 2, n) &&
- (n <= 7 || miller_rabin_test( 7, n)) &&
- (n <= 61 || miller_rabin_test(61, n)))
- return true;
- else
- return false;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement