fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4. class dcepc203
  5. {
  6.     static boolean isprime(long n){
  7.         long arr[]={2,3,5,7,11,13,17},j;
  8.         int i;
  9.         for(i=0;i<arr.length;i++)if(n==arr[i])return true;
  10.         BigInteger k,b,exp,mod=new BigInteger(""+n),check=new BigInteger("1"),c1=new BigInteger(""+(n-1));
  11.         for(i=0;i<arr.length;i++){
  12.             j=(n-1);
  13.             k= new BigInteger(""+arr[i]);
  14.             while((j%2)==0)j/=2;
  15.             exp=new BigInteger(""+j);
  16.             b=k.modPow(exp,mod);
  17.             while(j<=(n-1)){
  18.                 k=(b.multiply(b)).mod(mod);
  19.                 if(k.equals(check)&&!b.equals(check)&&!b.equals(c1) ){
  20.                     return false;
  21.                 }
  22.                 j*=2;
  23.                 b=k;
  24.             }
  25.             if(!b.equals(check))return false;
  26.         }
  27.         return true;
  28.     }
  29.     public static void main(String args[])throws Exception
  30.     {
  31.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  32.         boolean arr[]=new boolean[10000001];
  33.         int t,te,i=3,j,n,ans[]=new int[10000001];
  34.         long k;
  35.         for(i=2;i<100001;i++){
  36.             k=(2L*i*i)-1;
  37.             arr[i]=isprime(k);
  38.         }
  39.         ans[2]=0;
  40.         for(i=3;i<100001;i++){
  41.             ans[i]=ans[i-1];
  42.             if(arr[i-1])ans[i]++;
  43.         }
  44.         t=Integer.parseInt(br.readLine());
  45.         for(te=0;te<t;te++)
  46.         {
  47.             n=Integer.parseInt(br.readLine());
  48.             System.out.println(ans[n]);
  49.         }  
  50.         return;
  51.     }
  52. }
  53.  
Success #stdin #stdout 3.18s 380544KB
comments (?)
stdin
copy 
1
5
stdout
copy 
3
https://ideone.com/uaibzN
language:
Java (12.0.1)
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!