Java DSA Challenge: Check Prime Number with 6k ± 1 Rule

Java with DSA Challenge Day 5 Challenge Problem: Check Prime Number Today’s challenge was to determine whether a given integer n is a prime number or not. A prime number is a number greater than 1 that is divisible only by 1 and itself. Example: Input: n = 17 Output: True Explanation: 17 is divisible only by 1 and 17. This problem is a fundamental concept in number theory and serves as a great way to understand time complexity optimization in algorithms. Code Snippet // User function Template for Java class Solution { public static boolean prime(int n) { // 0 and 1 are not prime numbers if (n <= 1) return false; // 2 and 3 are prime numbers if (n <= 3) return true; // Eliminate multiples of 2 and 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check divisibility up to √n using 6k ± 1 rule for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; // number is prime } public static void main(String[] args) { int n1 = 17, n2 = 56; System.out.println(n1 + " is prime? " + prime(n1)); // true System.out.println(n2 + " is prime? " + prime(n2)); // false } } Code Explanation 1.Base Case Handling Numbers ≤ 1 are not prime, so we return false. 2. Small Prime Numbers 2 and 3 are prime by definition, so we return true. 3. Eliminate Multiples of 2 and 3 Any number divisible by 2 or 3 (except 2 and 3 themselves) cannot be prime. 4. Using the 6k ± 1 Rule All primes greater than 3 can be written as 6k ± 1. So, instead of checking every number, we only check divisibility for numbers of this form up to √n. This reduces unnecessary iterations and makes the code much faster. 5.Return True If no divisors are found, the number is prime. Complexity Time Complexity: O(√n) Space Complexity: O(1) Output 17 is prime? true 56 is prime? false Reflection This problem shows how even a simple concept like checking prime numbers can be optimized using mathematical insights like the 6k ± 1 rule. #Java #DSA #100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #Algorithms #LearnToCode #JavaDeveloper #SoftwareEngineering #DataStructures #Developer

  • graphical user interface

To view or add a comment, sign in

Explore content categories