JavaScript Challenges: Prime Numbers & Sophie Germain Primes

Prime Numbers

What are Prime Numbers?

A prime number is a whole number greater than 1 that cannot be exactly divided by any whole number other than itself and 1 (e.g. 2, 3, 5, 7, 11).

The number 5 is a prime number because its only factors are 1 and 5.

The number 4 is not a prime number because its factors are 1, 2 and 4.

Let's create a function that will return true if string is a prime number and return false if a number is not a prime.

isPrime(3); // true
isPrime(9); // false

Let’s create a function

function isPrime(num) {

}

A prime number is a number greater than 1. So, a number less than 1 is not a prime number.

function isPrime(num) {
  if (num <= 1) return false;
}

isPrime(-5); // false

The modulo operator is used to get the remainder after division. We are going to check if the num can be divided into other factors (except for 1 and itself) without leaving a remainder.

function isPrime(num) {
  if (num <= 1) return false;

  for (let i=2; i<num; i++) {
    if (num%i !== 0) return false;
  }
  return true;
}

Remember that 2 is a prime number.

function isPrime(num) {
  if (num <= 1) return false;
  if (num === 2) return true;

  for (let i=2; i<num; i++) {
    if (num%i === 0) return false;
  }
  return true;
}

isPrime(5); //true
isPrime(9); //false

What if we have a huge number?

isPrime(56669900033);

Our function will run slower. We can shorten the process by using the square root. For example,

number 121. The square root of 121 is 11. This means that 121 is not a prime number, because a prime number can only be divided equally by itself and 1. So, instead of iterating from 2 to 121, we can just iterate up to and including 11, the square root of 121.

Math.sqrt() find the square root of a number.

function isPrime(num) {
  if (num <= 1) return false;
  if (num === 2) return true;

  let numSqrt = Math.sqrt(num);

  for (let i=2; i<=numSqrt; i++) {
    if (num%i === 0) return false;
  }
  return true;
}

isPrime(5); //true
isPrime(121); //false

Sophie Germain Primes

If both p and 2p+1 are prime, then p is a Sophie Germain prime. For example, 2, 3, 5, 11, 23, 29, 41, 53, 83, 89…

5 is a prime number and 5*2+1=11

11 is a prime number too. So, both 5 and 11 are Sophie Germain prime numbers.

Let’s create a function that will return an array of Sophie Germain prime numbers from 2 until n.

We will use our isPrime() function from the previous example to check if the number is prime.

function getGermainPrimes(n) {
  let result = []; // an array of Sophie Germain prime numbers (our result)
  
  for (let i = 0; i <= n; i++) {
    if (isPrime(i) && isPrime(i*2 + 1)) { //if both i and 2i+1 are prime
      result.push(i); 
    }
  }

  return result;
}

getGermainPrimes(100); // [2, 3, 5, 11, 23, 29, 41, 53, 83, 89]

https://www.youtube.com/watch?v=XOgA8s2y7-Y/?embedable=true

I hope you found this helpful!