Smallest prime divisor of a number
Given a number N, find the smallest prime divisor of N.
Examples:
Input: 25
Output: 5Input: 31
Output: 31
Approach:
- Check if the number is divisible by 2 or not.
- Iterate from i = 3 to sqrt(N) and making a jump of 2.
- If any of the numbers divide N then it is the smallest prime divisor.
- If none of them divide, then N is the answer.
Below is the implementation of the above algorithm:
C++
// C++ program to count the number of // subarrays that having 1 #include <bits/stdc++.h> using namespace std; // Function to find the smallest divisor int smallestDivisor( int n) { // if divisible by 2 if (n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for ( int i = 3; i * i <= n; i += 2) { if (n % i == 0) return i; } return n; } // Driver Code int main() { int n = 31; cout << smallestDivisor(n); return 0; } |
Java
// Java program to count the number of // subarrays that having 1 import java.io.*; class GFG { // Function to find the smallest divisor static int smallestDivisor( int n) { // if divisible by 2 if (n % 2 == 0 ) return 2 ; // iterate from 3 to sqrt(n) for ( int i = 3 ; i * i <= n; i += 2 ) { if (n % i == 0 ) return i; } return n; } // Driver Code public static void main (String[] args) { int n = 31 ; System.out.println (smallestDivisor(n)); } } |
Python3
# Python3 program to count the number # of subarrays that having 1 # Function to find the smallest divisor def smallestDivisor(n): # if divisible by 2 if (n % 2 = = 0 ): return 2 ; # iterate from 3 to sqrt(n) i = 3 ; while (i * i < = n): if (n % i = = 0 ): return i; i + = 2 ; return n; # Driver Code n = 31 ; print (smallestDivisor(n)); # This code is contributed by mits |
C#
// C# program to count the number // of subarrays that having 1 using System; class GFG { // Function to find the // smallest divisor static int smallestDivisor( int n) { // if divisible by 2 if (n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for ( int i = 3; i * i <= n; i += 2) { if (n % i == 0) return i; } return n; } // Driver Code static public void Main () { int n = 31; Console.WriteLine(smallestDivisor(n)); } } // This code is contributed // by Sach_Code |
PHP
<?php // PHP program to count the number // of subarrays that having 1 // Function to find the smallest divisor function smallestDivisor( $n ) { // if divisible by 2 if ( $n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for ( $i = 3; $i * $i <= $n ; $i += 2) { if ( $n % $i == 0) return $i ; } return $n ; } // Driver Code $n = 31; echo smallestDivisor( $n ); // This code is contributed by Sachin ?> |
Javascript
<script> // javascript program to count the number of // subarrays that having 1 // Function to find the smallest divisor function smallestDivisor(n) { // if divisible by 2 if (n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for ( var i = 3; i * i <= n; i += 2) { if (n % i == 0) return i; } return n; } // Driver Code var n = 31; document.write(smallestDivisor(n)); // This code is contributed by todaysgaurav </script> |
Output:
31
How to efficiently find prime factors of all numbers till n?
Please refer Least prime factor of numbers till n
Time Complexity: O(sqrt(N)), as we are using a loop to traverse sqrt (N) times. As the condition is i*i<=N, on application of sqrt function on both the sides we get sqrt (i*i) <= sqrt(N), which is i<= sqrt(N), therefore the loop will traverse for sqrt(N) times.
Auxiliary Space: O(1), as we are not using any extra space.