2

I came across a Java program which finds whether the given number is a prime. here is the code.

class FindPrime {
    public static void main(String args[]) {
        int num;
        boolean isPrime;
        num = 14;

        if (num < 2) 
          isPrime = false;
        else 
          isPrime = true;

        for (int i = 2; i <= num / i; i++) {
            if ((num % i) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) 
          System.out.println("Prime");
        else 
          System.out.println("Not Prime");
    }
}

Here, I'm not sure why the condition i <= num/i is used in the for loop. Can someone please explain me?

KYL3R
  • 3,877
  • 1
  • 12
  • 26
Madhusudan
  • 23
  • 1
  • 4

7 Answers7

2

The limiting condition i <= num / i is a performance optimisation:

Given e.g. num = 11 and i = 3, we have so far checked if 11 can be divided by 2 (no) and now are moving to 3 and we should check it, the answer is no it cannot be divided by 3. Now we are moving to 4, should we still check if 11 can be divided by it? Such a division will yield 2.75, a value smaller than 3 that we have already checked. Any higher i will yield even smaller values all of which we have already checked, so there is no sense checking further. We know the answer by now.

Oleg Sklyar
  • 9,834
  • 6
  • 39
  • 62
1

Do not forget, that for loop like for(A;B;C) expression A is calculated once at the beginning of the loop, expression B is calculated every loop starting from first, expression C is calculated started from second loop.

So it is better to move deviation from section B to section A.

i < num / i is performance optimization, moreover it is enough to check first Math.sqrt(num) elements.

public static boolean isPrime(int val) {
    if (val < 2)
        return false;

    for (int i = 2, max = (int)Math.sqrt(val); i <= max; i++)
        if (val % i == 0)
            return false;

    return true;
}
Oleg Cherednik
  • 17,377
  • 4
  • 21
  • 35
  • for better performance, you can check the number id divide by 2 or not then in for loop start with 3 and increase the i with +2. It will skip all even number so the computation of prime number will faster two time. – Vpn_talent Dec 28 '18 at 07:39
1

i <= num/i it's like doing i <= sqrt(num).
If num is not a prime, we can factorize it into num = a * b.
If a factor of num is greater then the the square root of num, the other one must be less then the square root of num.
If both were greater than it, then its product would be greater than num.

RubenDG
  • 1,365
  • 1
  • 13
  • 18
0

This is the better way to check the prime number or not 

package com.practice.competitive.maths;

import java.util.Scanner;

public class CheckPrime {

    public static void main(String[] args) {

        try(Scanner scanner = new Scanner(System.in)) {
            int testCases = scanner.nextInt();
            long number = scanner.nextLong();
            String result = compute(number);
            System.out.println(result);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static String compute(long number) {
        if(number > 0 &&  number % 2 == 0)
            return "No";
        long sqrt = floorSqrt(number);
        for(long i = 3; i<sqrt;i+=2) {
            if(number % i == 0)
                return "No";
        }
        return "Yes";
    }

    private static long floorSqrt(long number) {
        if(number == 0 || number == 1)
            return number;
        long start = 0;
        long end = number;
        long answer = 0;
        while (start <= end) {
            long mid = (start + end)/2;
            if(mid*mid == number)
                return mid;
            if(mid*mid < number) {
                start = mid+1;
                answer = mid;
            }else {
                end = mid-1;
            }
        }
        return answer;
    }

}
Vpn_talent
  • 1,290
  • 12
  • 21
0

The below solution prints out all prime numbers up to the number provided by the user, using the Sieve of Sundaram:

Note, that you might have an OutOfMemoryError for a large input.

public static void isPrime(int num) {
    int k = (num - 2) / 2;
    int[] a = new int[k + 1];
    for (int i = 1; i < k + 1; i++) {
        int j = i;
        while ((i + j + 2 * i * j) <= k) {
            a[i + j + 2 * i * j] = 1;
            j += 1;
        }
    }
    if (num > 2) {
        System.out.println(2);
    }

    for (int l = 1; l < k + 1; l++) {
        if (a[l] == 0) {
            System.out.println((2 * l + 1));
        }
    }
}
0

it is not wise to add for loops in the program since they give u a time complexity which is greater O(n) linear time complexity but if statements would be wise here is an example

// code contributed by akoyama koke

public class prime
{
    public static void main(String[] args) 
    {
        int []arry={1,23,71,3,4,5,6,8,21};
        int n=arry[8];
        if(n%2==0)
        {
            System.out.print("number is even:"+" "+n);
        }
        else if(n%2!=0)
        {
            if(n%3!=0 && n%5!=0 && n%7!=0)
            {
                 System.out.print("number is prime:"+" "+n);
            }
            else
            {
                System.out.print("number is odd and not prime:"+"  "+n);
            }
        }
        else
         System.out.println("number either decimal or a negative not catared for:"+" "+n);
    }
}
user14752462
  • 1
-1

yes it is. The middle part of the for loop is always evaluated and the loop content runs only if the evaluation give a true value. In your case, the loop will stop on its first cycle since the module of 14/2 is 0, therefore it will run the if body which set the boolean to false and exit the loop.

Robdll
  • 5,865
  • 7
  • 31
  • 51