Check If a Number Is Prime

Check Number prime in JavaScript

Time complexity: O(sqrt(n))

Space complexity: O(1)

const isPrime = num => {
    for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num % i === 0) return false; 
    return num > 1;
}

How to check if a 10 digit number is prime or not?

public static void main(String[] args) {
    try (Scanner scan = new Scanner(System.in)) {
        System.out.print("Enter: ");
        long val = scan.nextLong();
        long t1 = System.currentTimeMillis();
        System.out.println(isPrime.test(val) ? "yes" : "no");
        System.out.println("took " + (System.currentTimeMillis() - t1) + " millis");
    }
}

static final LongPredicate isPrime = val -> {
    if (val < 2)
        return false;

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

    return true;
};

Output:

Enter: 999999937
yes
took 1 millis

How to check if a number is prime? and if is not, how to increment the number until the function returns the next prime number?

Looks like the site only allows you to have the function and nothing else. Specifically in this situation: no separate functions. So if I put your checkPrime function inside myFunction it will pass successfully.

function myFunction(number) {
  function checkPrime(number) {
    for (var i = 2; i < number; i++) {
      if (number % i === 0) {
        return false;
      }
    }
    return true;
  }
  if (checkPrime(number)) {
    return number;
  } else {
    while (checkPrime(number) === false) {
      number++;
    }
  }
  return number;
}

To find a number is prime, Why checking till n/2 is better. What is the reason for avoiding numbres in second half of n

Because, the smallest multiple that will not make it a prime is 2. If you have checked all the numbers from 0 to n/2, what multiple is left that could possibly work? If multiple by 2 is bigger than n, then a multiple of 3 or 4 etc will also be bigger than n.

So the largest factor for any number N must be <= N/2

So yes take N/2, and check all integers smaller or equal to N/2. So for 11 you would check all integers smaller than 5.5, i.e. 1, 2, 3, 4 and 5.

The square root is explained here:
Why do we check up to the square root of a prime number to determine if it is prime?

And this question has been asked before.

Validate if input number is prime

The sympy.isprime() is a built-in function under the SymPy module and can be utilized for checking of possible prime numbers. It is a direct function and returns True if the number to be checked is prime and False if the number is not prime.

>>> import simpy
  
>>> sympy.isprime(8)

False

>>> sympy.isprime(11)

True

or else define a function like this

>>> def isPrime(k):
    
    # 1 is not prime number
    if k==1:
        return False

    # 2, 3 are prime
    if k==2 or k==3: 
        return True

    # even numbers are not prime
    if k%2==0: 
        return False

    # check all numbers till square root of the number , 
    # if the division results in remainder 0
    # (skip 2 since we dont want to divide by even numbers)

    for i in range(3, int(k**0.5)+1, 2):
        if k%i==0:
            return False

    return True

>>> print(isPrime(13))

True

>>> print(isPrime(18))

False

---

Related Topics