Prime Numbers What are ? Prime Numbers 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). A prime number The number 5 is a because its only factors are 1 and 5. prime number The number 4 is because its factors are 1, 2 and 4. not a prime number Let's create a function that will return if string is a and return if a number is not a . true prime number false prime isPrime(3); // true
isPrime(9); // false Let’s create a function function isPrime(num) {

} A is a number greater than 1. So, a number less than 1 is not a prime number prime number. function isPrime(num) {
  if (num <= 1) return false;
} isPrime(-5); // false The is used to get the remainder after division. We are going to check if the can be divided into other factors (except for 1 and itself) without leaving a remainder. modulo operator num function isPrime(num) {
  if (num <= 1) return false;

  for (let i=2; i<num; i++) {
    if (num%i !== 0) return false;
  }
  return true;
} that 2 is a Remember 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 For example, square root. number The square root of is . This means that is , because a can only be divided equally by itself and 1. So, instead of iterating from , we can just iterate up to and including , the square root of . 121. 121 11 121 not a prime number prime number 2 to 121 11 121 find the square root of a number. Math.sqrt() 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 . For example, Sophie Germain prime 2, 3, 5, 11, 23, 29, 41, 53, 83, 89… is a and 5 prime number 5*2+1=11 is a too. So, both and are 11 prime number 5 11 Sophie Germain prime numbers. Let’s create a function that will return an array of from until Sophie Germain prime numbers 2 n. We will use our function from the previous example to check if the number is prime. isPrime() 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!

Buy Me a Coffee

Hire Me

Portfolio

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

JavaScript Challenges: Prime Numbers & Sophie Germain Primes

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps