Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What are Prime Numbers?
3.
Some Interesting Facts about Prime Numbers
3.1.
Infinitude
3.2.
Prime Gap
3.3.
Application in Cryptography
4.
Properties of Prime Numbers
4.1.
Fundamental Theorem of Arithmetic 
4.2.
Primality Test
4.3.
Distribution 
5.
Prime Numbers and Co-prime Numbers
5.1.
Definition of Co-prime Numbers
5.2.
Key Role in Algorithms 
5.3.
Euclidean Algorithm 
6.
JavaScript Prime & Co-Prime Checker Program with User Interface
6.1.
1. HTML Structure
6.2.
HTML
6.3.
2. JavaScript (numberChecker.js)
6.4.
JavaScript
7.
Program Description
7.1.
How to Use
8.
Time and Space Complexity of Prime Number Algorithms
8.1.
Time Complexity
8.2.
Space Complexity
9.
Frequently Asked Questions
9.1.
Why is checking for prime numbers important in programming?
9.2.
How does the Euclidean Algorithm help in identifying co-prime numbers?
9.3.
Can the prime number checking algorithm be optimized further in JavaScript?
10.
Conclusion
Last Updated: Mar 27, 2024
Easy

Prime Number in Javascript

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

When diving into the programming world, especially with JavaScript, prime numbers emerge as a fascinating & essential concept. These unique numbers hold a special place in both mathematics & coding, offering intriguing challenges & opportunities for optimization. 

prime number in javascript

Their significance extends beyond academic interest, playing a crucial role in areas like cryptography, making understanding them vital for aspiring coders.

What are Prime Numbers?

Prime numbers are integers greater than 1, which have no divisors other than 1 & themselves. In other words, a prime number can't be formed by multiplying two smaller natural numbers. This definition sets the foundation for various algorithms & mathematical theories.

In JavaScript, recognizing prime numbers can be a crucial skill. Whether you're optimizing a function or working on a complex algorithm, knowing how to identify & manipulate these numbers can be immensely beneficial.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Some Interesting Facts about Prime Numbers

Prime numbers, often described as the "atoms" of mathematics, harbor fascinating characteristics that intrigue mathematicians & programmers alike. Here are a few captivating facts:

Infinitude

 A remarkable property of prime numbers is their infinitude. There's no largest prime number. The ancient proof by Euclid around 300 BC still stands strong today.

Prime Gap

The gap between prime numbers grows as they get larger, but surprisingly, there are always prime pairs (twin primes) that are only two numbers apart.

Application in Cryptography

In modern technology, primes are the backbone of encryption algorithms, including RSA, one of the first public-key cryptosystems.

Properties of Prime Numbers

Prime numbers have unique properties that make them an essential subject in both mathematics & computer science. Here’s a look at some of these properties:

Fundamental Theorem of Arithmetic 

Every integer greater than 1 is either a prime number or can be uniquely represented as a product of prime numbers, known as its prime factorization. This theorem is a cornerstone in number theory.

Primality Test

Determining whether a number is prime or not is a fundamental task in algorithms. In JavaScript, this often involves iterating through possible divisors & checking for divisibility.

Distribution 

Primes become less frequent as numbers get larger. However, there needs to be a simple formula for finding the nth prime number, making their distribution a fascinating study area.

Prime Numbers and Co-prime Numbers

In integers, prime numbers often share the stage with another exciting concept: co-prime numbers. Here’s an insight into their relationship:

Definition of Co-prime Numbers

Two numbers are said to be co-prime (or relatively prime) if they have no common factors other than 1. Interestingly, a prime number & any other number not divisible by it are always co-prime.

Key Role in Algorithms 

In JavaScript, understanding co-prime numbers can be crucial for algorithms that rely on number theory, such as those in cryptography. They are fundamental in algorithms requiring modular arithmetic.

Euclidean Algorithm 

This is a popular method to find the Greatest Common Divisor (GCD) of two numbers, which in turn helps identify if the numbers are co-prime. JavaScript implementations of this algorithm showcase efficient problem-solving strategies.

JavaScript Prime & Co-Prime Checker Program with User Interface

1. HTML Structure

  • HTML

HTML

<!DOCTYPE html>

<html>

<head>

   <title>Prime & Co-Prime Number Checker</title>

</head>

<body>

   <h2>Prime & Co-Prime Number Checker in JavaScript</h2>

   <label for="numberInput">Enter a number:</label>

   <input type="number" id="numberInput" />

   <button onclick="performCheck()">Check</button>

   <p id="primeResult"></p>

   <p id="coPrimeResult"></p>

 <script src="numberChecker.js"></script>

</body>

</html>

2. JavaScript (numberChecker.js)

  • JavaScript

JavaScript

function isPrime(num) {

   if (num <= 1) return false;

   if (num === 2) return true;

   if (num % 2 === 0) return false;

   for (let i = 3; i <= Math.sqrt(num); i += 2) {

       if (num % i === 0) return false;

   }

   return true;

}



function areCoPrime(num1, num2) {

   function gcd(a, b) {

       if (!b) return a;

       return gcd(b, a % b);

   }

   return gcd(num1, num2) === 1;

}


function performCheck() {

   const num = parseInt(document.getElementById('numberInput').value);

   const primeResult = isPrime(num) ? `${num} is a prime number.` : `${num} is not a prime number.`;

   document.getElementById('primeResult').innerText = primeResult;

   const coPrimeResult = [];

   for (let i = 1; i <= 10; i++) {

       if (areCoPrime(num, i)) {

           coPrimeResult.push(i);

       }

   }

   document.getElementById('coPrimeResult').innerText = `Numbers co-prime with ${num}: ${coPrimeResult.join(', ')}`;

}

Output

Output

Program Description


The HTML provides a user interface with an input field for the number and a button to trigger the checks.

The JavaScript file contains:

  • isPrime(num): Function to check if a number is prime.
     
  • areCoPrime(num1, num2): Function to check if two numbers are co-prime.
     
  • performCheck(): Function that executes when the button is clicked. It checks if the entered number is prime and finds numbers (1-10) that are co-prime with it, displaying the results.

How to Use

  • Open the HTML file in a web browser.
     
  • Enter a number in the input field.
     
  • Click the "Check" button to see the results for prime and co-prime checks.

Time and Space Complexity of Prime Number Algorithms

When implementing prime number algorithms in JavaScript, understanding their time and space complexity is crucial for evaluating efficiency and performance.

Time Complexity

  • Basic Prime Checking: The isPrime function we discussed involves checking divisibility up to the square root of the number. This results in a time complexity of O(√n). This is because in the worst case, the loop runs approximately √n times.
     
  • Co-Prime Checking: The areCoPrime function uses the Euclidean algorithm for finding the GCD. The time complexity of this algorithm is O(log min(a, b)), where a and b are the two numbers being compared.

Space Complexity

  • Prime Checking: The space complexity for the prime checking algorithm is O(1) – constant space. It does not use additional space that scales with the input size, only a fixed number of variables.
     
  • Co-Prime Checking: Similarly, the co-prime checking algorithm has a space complexity of O(1). The recursive calls of the Euclidean algorithm do not significantly increase the space usage.

Frequently Asked Questions

Why is checking for prime numbers important in programming?

Prime numbers play a key role in various algorithms, especially in cryptography and security. In programming, algorithms for prime number checks are used to enhance skills in logical thinking, optimization, and understanding of fundamental mathematical concepts.

How does the Euclidean Algorithm help in identifying co-prime numbers?

The Euclidean Algorithm is used to find the Greatest Common Divisor (GCD) of two numbers. If the GCD is 1, the numbers are co-prime. This algorithm is efficient and widely used in programming for its simplicity and effectiveness in calculating GCD.

Can the prime number checking algorithm be optimized further in JavaScript?

Yes, optimizations such as skipping even numbers (beyond 2) and implementing more advanced mathematical theories like the Sieve of Eratosthenes can make the algorithm more efficient, especially for larger numbers.

Conclusion

Exploring prime numbers in JavaScript not only enhances your understanding of a fundamental mathematical concept but also sharpens your programming skills. From simple checks to understanding their role in co-prime pairs, and grasping the intricacies of algorithm complexities, this journey offers invaluable insights for coding students. As you delve deeper, remember that these concepts form the backbone of many advanced algorithms, particularly in fields like cryptography, making them an essential part of your programming toolkit.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. 

Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
What Is Timestamp
Next article
Block Statement in JavaScript
Live masterclass