CODEWITHSUNDEEP
javamathtime-complexityprimes
cain
cain

Reputation: 61

Java-Why these two are giving different outputs for calculating prime numbers of form k^2+1?

I wrote two programs for my lab work for finding primes of form k^2 +1 less than 1000000 in two different ways to have better time complexity in 2nd program but i am getting different answers in both. Can someone tell me why?In first we are first checking if its a prime(n) and then checking if its perfect square(n-1). In second we are directly checking form k^2+1 for k less than sqrt(1000000)-1 and increasing the count. But both produce different answers.Which method is right for counting primes of form k^2+1 under 1000000?

First Program

 public class KSqPlus1
    {

    public static void main(String [] args)
  { 
     int k = 2;
    for (int n = 11; n < 1000000; n += 2)
       if (isPrime (n))
         if (isPerfectSquare (n - 1))
         {   k ++; 

       }

     System.out.println (k);  

  }

   public static boolean isPrime(int n)
   {
     for(int divisor=3;divisor*divisor<=n;divisor+=2)
         if(n%divisor==0)
           return false;
        return true;
   }
  public static boolean isPerfectSquare (int n)
     {
          for(int divisor=2;divisor*divisor<=n;divisor+=2)
         if(divisor * divisor < n) continue;
          else if (divisor * divisor == n ) return true;
          return false;

     }
 }

2nd Program

import java.lang.Math;
public class PrimeArrays1
{

  public static void main(String [] args)
  {

    int count=2;int k;
    for(k=3;k<(Math.sqrt(1000000)-1);k++)
    { int x=k*k+1;
     if(isPrime(x))
     {
      count++;

     }
    }
     System.out.println(count);



  }

   public static boolean isPrime(double n)
   {
     for(int divisor=3;divisor*divisor<=n;divisor+=2)
     if(n%divisor==0)
     return false;
     return true;
   }

 }

EDIT:: Below is the correct isPrime function..now the programs are giving same answer :)

public static boolean isPrime(int n)
   {
     for(int divisor=2;divisor*divisor<=n;divisor+=1)
         if(n%divisor==0)
           return false;
        return true;
   }

Upvotes: 2

Views: 98

Answers (1)

Henry
Henry

Reputation: 43798

This method

  public static boolean isPerfectSquare (int n)
     {
          for(int divisor=2;divisor*divisor<=n;divisor+=2)
         if(divisor * divisor < n) continue;
          else if (divisor * divisor == n ) return true;
          return false;

     }

will return true only if n is a square of an even number. I guess you want to check if it is a square of any number.

Similarly, the method

   public static boolean isPrime(double n)
   {
     for(int divisor=3;divisor*divisor<=n;divisor+=2)
     if(n%divisor==0)
     return false;
     return true;
   }

Does not check for factors of 2, so 4, 8, ... return true.

Upvotes: 2

Related Questions