Given an integer N. The task is to find check if the Sum of total number of factors from 1 to N is even or odd i.e., sum % 2 = 0 or 1.
Examples:
Input: N = 3
Output: Odd
Explanation: 1 has 1 factor, 2 has 2 factors (1, 2) and 3 has 2 factors (1, 3),
Hence, total number of factors is 5 which is odd.Input: N = 4
Output: Even
Explanation: 1 has 1 factor, 2 has 2 factors (1, 2), 3 has 2 factors (1, 3) and 4 has 3 factors (1, 2, 4),
Hence, a total of 8 factors which is even.
Naive approach: The basic idea to solve the problem is to first Find all the factors of the numbers from 1 to N and then store their sum and check if the sum is even or odd.
Below is the implementation of the above approach.
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the factors int factor( int n) { int count = 0; // Counting the factors for // all the numbers. for ( int i = 1; i <= n; i++) { // Counting the factors // for number i for ( int j = 1; j < sqrt (n) + 1; j++) { if (i % j == 0) { if (i / j == j) { count += 1; } else { count += 2; } count %= 2; } } } // Return the count return count; } // Driver Code int main() { int N = 4; // Function call if (factor(N)) cout << "Odd" ; else cout << "Even" ; return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { // Function to find the factors static int factor( int n) { int count = 0 ; // Counting the factors for // all the numbers. for ( int i = 1 ; i <= n; i++) { // Counting the factors // for number i for ( int j = 1 ; j < Math.sqrt(n) + 1 ; j++) { if (i % j == 0 ) { if (i / j == j) { count += 1 ; } else { count += 2 ; } count %= 2 ; } } } // Return the count return count; } // Driver Code public static void main (String[] args) { int N = 4 ; // Function call if (factor(N) != 0 ) System.out.print( "Odd" ); else System.out.print( "Even" ); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach: # Function to find the factors import math def factor(n): count = 0 # Counting the factors for # all the numbers. for i in range ( 1 , n + 1 ): # Counting the factors # for number i for j in range ( 1 ,math.floor(math.sqrt(n) + 1 )): if (i % j = = 0 ): if (i / j = = j): count + = 1 else : count + = 2 count % = 2 # Return the count return count # Driver Code N = 4 # Function call if (factor(N)): print ( "Odd" ) else : print ( "Even" ) # This code is contributed by shinjanpatra |
C#
// C# code for the above approach: using System; class GFG { // Function to find the factors static int factor( int n) { int count = 0; // Counting the factors for // all the numbers. for ( int i = 1; i <= n; i++) { // Counting the factors // for number i for ( int j = 1; j < Math.Sqrt(n) + 1; j++) { if (i % j == 0) { if (i / j == j) { count += 1; } else { count += 2; } count %= 2; } } } // Return the count return count; } // Driver Code public static void Main() { int N = 4; // Function call if (factor(N) != 0) Console.Write( "Odd" ); else Console.Write( "Even" ); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScripy code for the above approach: // Function to find the factors function factor(n) { let count = 0; // Counting the factors for // all the numbers. for (let i = 1; i <= n; i++) { // Counting the factors // for number i for (let j = 1; j < Math.sqrt(n) + 1; j++) { if (i % j == 0) { if (i / j == j) { count += 1; } else { count += 2; } count %= 2; } } } // Return the count return count; } // Driver Code let N = 4; // Function call if (factor(N)) document.write( "Odd" ); else document.write( "Even" ); // This code is contributed by shinjanpatra </script> |
Even
Time Complexity: O(N*sqrt(N))
Auxiliary Space: O(1)
Better Approach: The idea to solve the problem is the same as of the naive apporach. But finding factors is done in more efficient way here. We will be counting factors in O(n1/3) time complexity using the apporach mentioned and discussed in this article: Count Divisors of n in O(n^1/3).
Algorithm:
- Define a function SieveOfEratosthenes() that takes an integer n, a boolean array prime[], a boolean array primesquare[] and an integer array a[] as input.
- Initialize all entries in prime[] to true.
- Initialize all entries in primesquare[] to false.
- Set prime[1] to false.
- Using Sieve of Eratosthenes algorithm, set prime[i] to false if i is not a prime.
- Using Sieve of Eratosthenes algorithm, set primesquare[i] to true if i is a square of a prime.
- Store all prime numbers less than or equal to n in the integer array a[].
- Define a function factor() that takes an integer n as input.
- If n is 1, return 1.
- Call the SieveOfEratosthenes() function with parameters n, prime[], primesquare[], and a[].
- Initialize ans to 1.
- Loop through all prime numbers in a[].
- If the cube of a[i] is greater than n, break from the loop.
- Calculate the power of a[i] in n.
- Update ans by multiplying it with cnt, which is the power of a[i] in n plus 1.
- If n is still greater than 1, it has a prime factor greater than the cube root of n.
- If n is prime, update ans by multiplying it with 2.
- If n is a square of a prime, update ans by multiplying it with 3.
- If n is neither prime nor a square of a prime, update ans by multiplying it with 4.
- Return ans..
Below is the implementation of the above approach:
C++
// C++ code for the approach #include <bits/stdc++.h> using namespace std; void SieveOfEratosthenes( int n, bool prime[], bool primesquare[], int a[]) { //For more details check out: https://www.neveropen.co.uk/sieve-of-eratosthenes/ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. for ( int i = 2; i <= n; i++) prime[i] = true ; // Create a boolean array "primesquare[0..n*n+1]" // and initialize all entries it as false. A value // in squareprime[i] will finally be true if i is // square of prime, else false. for ( int i = 0; i <= (n * n + 1); i++) primesquare[i] = false ; // 1 is not a prime number prime[1] = false ; for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true ) { // Update all multiples of p starting from p * p for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } int j = 0; for ( int p = 2; p <= n; p++) { if (prime[p]) { // Storing primes in an array a[j] = p; // Update value in primesquare[p*p], // if p is prime. primesquare[p * p] = true ; j++; } } } // Function to count factors int factor( int n) { // If number is 1, then it will have only 1 // as a factor. So, total factors will be 1. if (n == 1) return 1; bool prime[n + 1], primesquare[n * n + 1]; int a[n]; // for storing primes upto n // Calling SieveOfEratosthenes to store prime // factors of n and to store square of prime // factors of n SieveOfEratosthenes(n, prime, primesquare, a); // ans will contain total number of distinct // divisors int ans = 1; // Loop for counting factors of n for ( int i = 0;; i++) { // a[i] is not less than cube root n if (a[i] * a[i] * a[i] > n) break ; // Calculating power of a[i] in n. int cnt = 1; // cnt is power of prime a[i] in n. while (n % a[i] == 0) // if a[i] is a factor of n { n = n / a[i]; cnt = cnt + 1; // incrementing power } // Calculating the number of divisors // If n = a^p * b^q then total divisors of n // are (p+1)*(q+1) ans = ans * cnt; } // if a[i] is greater than cube root of n // First case if (prime[n]) ans = ans * 2; // Second case else if (primesquare[n]) ans = ans * 3; // Third case else if (n != 1) ans = ans * 4; return ans; // Total factors } // Driver Code int main() { int N = 4; long long int sum = 0; for ( int i = 1; i <= N; i++){ sum += factor(i); } // Function call if (sum % 2 != 0) cout << "Odd" ; else cout << "Even" ; return 0; } |
Java
import java.util.Arrays; public class Main { // Function to perform the Sieve of Eratosthenes algorithm static void SieveOfEratosthenes( int n, boolean [] prime, boolean [] primesquare, int [] a) { Arrays.fill(prime, true ); Arrays.fill(primesquare, false ); prime[ 1 ] = false ; for ( int p = 2 ; p * p <= n; p++) { if (prime[p]) { for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } int j = 0 ; for ( int p = 2 ; p <= n; p++) { if (prime[p]) { a[j] = p; primesquare[p * p] = true ; j++; } } } // Function to count the number of factors of a given number static int factor( int n) { if (n == 1 ) return 1 ; boolean [] prime = new boolean [n + 1 ]; boolean [] primesquare = new boolean [n * n + 1 ]; int [] a = new int [n]; // Calculate prime numbers using Sieve of Eratosthenes SieveOfEratosthenes(n, prime, primesquare, a); int ans = 1 ; for ( int i = 0 ;; i++) { if (a[i] * a[i] * a[i] > n) break ; int cnt = 1 ; while (n % a[i] == 0 ) { n = n / a[i]; cnt = cnt + 1 ; } ans = ans * cnt; } // Check for remaining prime or primesquare factors if (prime[n]) ans = ans * 2 ; else if (primesquare[n]) ans = ans * 3 ; else if (n != 1 ) ans = ans * 4 ; return ans; } // Driver code public static void main(String[] args) { int N = 4 ; long sum = 0 ; // Calculate the sum of factors for numbers from 1 to N for ( int i = 1 ; i <= N; i++) { sum += factor(i); } // Check if the sum is odd or even and print the result if (sum % 2 != 0 ) System.out.println( "Odd" ); else System.out.println( "Even" ); } } |
Python3
# Function to find all prime numbers up to a given number n using Sieve of Eratosthenes def sieve_of_eratosthenes(n): # Initialize a boolean list "prime" and assume all numbers are prime prime = [ True ] * (n + 1 ) prime[ 0 ] = prime[ 1 ] = False # 0 and 1 are not primes # Mark multiples of prime numbers as not prime for p in range ( 2 , int (n * * 0.5 ) + 1 ): if prime[p]: for i in range (p * p, n + 1 , p): prime[i] = False # Return a list of prime numbers return [p for p in range ( 2 , n + 1 ) if prime[p]] # Function to calculate the total number of factors for a given number n def factor(n): if n = = 1 : return 1 # If number is 1, it has only 1 factor primes = sieve_of_eratosthenes(n) # Find prime numbers up to n ans = 1 # Count factors for each prime factor and multiply to get total factors for p in primes: cnt = 0 while n % p = = 0 : n / / = p cnt + = 1 ans * = cnt + 1 # If n is still greater than 1, it is a prime factor itself if n > 1 : ans * = 2 return ans #Driver code def main(): N = 4 total_factors_sum = sum (factor(i) for i in range ( 1 , N + 1 )) # Check if the sum of total factors is odd or even and print the result if total_factors_sum % 2 ! = 0 : print ( "Odd" ) else : print ( "Even" ) if __name__ = = "__main__" : main() |
C#
using System; class MainClass { // Function to perform the Sieve of Eratosthenes algorithm static void SieveOfEratosthenes( int n, bool [] prime, bool [] primesquare, int [] a) { Array.Fill(prime, true ); Array.Fill(primesquare, false ); prime[1] = false ; for ( int p = 2; p * p <= n; p++) { if (prime[p]) { for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } int j = 0; for ( int p = 2; p <= n; p++) { if (prime[p]) { a[j] = p; primesquare[p * p] = true ; j++; } } } // Function to count the number of factors of a given number static int Factor( int n) { if (n == 1) return 1; bool [] prime = new bool [n + 1]; bool [] primesquare = new bool [n * n + 1]; int [] a = new int [n]; // Calculate prime numbers using Sieve of Eratosthenes SieveOfEratosthenes(n, prime, primesquare, a); int ans = 1; for ( int i = 0; ; i++) { if (a[i] * a[i] * a[i] > n) break ; int cnt = 1; while (n % a[i] == 0) { n = n / a[i]; cnt = cnt + 1; } ans = ans * cnt; } // Check for remaining prime or primesquare factors if (prime[n]) ans = ans * 2; else if (primesquare[n]) ans = ans * 3; else if (n != 1) ans = ans * 4; return ans; } // Driver code public static void Main( string [] args) { int N = 4; long sum = 0; // Calculate the sum of factors for numbers from 1 to N for ( int i = 1; i <= N; i++) { sum += Factor(i); } // Check if the sum is odd or even and print the result if (sum % 2 != 0) Console.WriteLine( "Odd" ); else Console.WriteLine( "Even" ); } } |
Javascript
// Function to find prime factors of a number and count its factors function factor(n) { if (n === 1) { return 1; } const prime = new Array(n + 1).fill( true ); const primesquare = new Array(n * n + 1).fill( false ); const a = []; // Function to calculate prime factors using Sieve of Eratosthenes function SieveOfEratosthenes() { prime[0] = prime[1] = false ; for (let p = 2; p * p <= n; p++) { if (prime[p]) { for (let i = p * p; i <= n; i += p) { prime[i] = false ; } } } let j = 0; for (let p = 2; p <= n; p++) { if (prime[p]) { a[j] = p; primesquare[p * p] = true ; j++; } } } SieveOfEratosthenes(); let ans = 1; for (let i = 0;; i++) { if (a[i] * a[i] * a[i] > n) { break ; } let cnt = 1; while (n % a[i] === 0) { n = n / a[i]; cnt = cnt + 1; } ans = ans * cnt; } if (prime[n]) { ans = ans * 2; } else if (primesquare[n]) { ans = ans * 3; } else if (n !== 1) { ans = ans * 4; } return ans; // Total factors } // Driver Code function main() { const N = 4; let sum = 0; for (let i = 1; i <= N; i++) { sum += factor(i); } // Check if the sum of factors is even or odd if (sum % 2 !== 0) { console.log( "Odd" ); } else { console.log( "Even" ); } } main(); |
Even
Time Complexity: O( n * n1/3 ) where n is the size of the input integer.
Space Complexity: O(n) as boolean arrays prime and primesquare has been created. Here, n is the size of the input integer.
Efficient Approach: The idea to solve the problem efficiently is based on the following observation.
As, all numbers except perfect squares, have an even number of factors. So, the concern is only perfect squares.
Find the number of perfect squares that lie between 1 to N.
If the number of perfect squares is odd then total number of factors is odd, otherwise, even.
Follow the steps to solve the problem:
- Declare any count variable to store the factors of a number and initialize it with 0.
- Update count with the total number of perfect squares from 1 to N which is the same as the sqrt(N).
- Check if count is even or odd and return 0 or 1 accordingly.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the count of factors int factor( int N) { int count = 0; // Finding out the number of // perfect squares that lie // between 1 to N. count = ( int ) sqrt (N); count = count % 2; return count; } // Driver code int main() { int N = 4; // Function call if (factor(N)) cout << "Odd" ; else cout << "Even" ; return 0; } |
Java
// JAVA code for the above approach: import java.util.*; class GFG { // Function to find the count of factors public static int factor( int N) { int count = 0 ; // Finding out the number of // perfect squares that lie // between 1 to N. count = ( int )Math.sqrt(N); count = count % 2 ; return count; } // Driver code public static void main(String[] args) { int N = 4 ; // Function call if (factor(N) != 0 ) System.out.print( "Odd" ); else System.out.print( "Even" ); } } // This code is contributed by Taranpreet |
Python3
# Python code for the above approach: # Function to find the count of factors import math def factor(N): count = 0 # Finding out the number of # perfect squares that lie # between 1 to N. count = math.floor(math.sqrt(N)) count = count % 2 return count # Driver code N = 4 # Function call if (factor(N)): print ( "Odd" ) else : print ( "Even" ) # This code is contributed by shinjanpatra. |
C#
// C# code for the above approach: using System; class GFG { // Function to find the count of factors static int factor( int N) { int count = 0; // Finding out the number of // perfect squares that lie // between 1 to N. count = ( int )Math.Sqrt(N); count = count % 2; return count; } // Driver code public static void Main() { int N = 4; // Function call if (factor(N) != 0) Console.Write( "Odd" ); else Console.Write( "Even" ); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach: // Function to find the count of factors function factor(N) { let count = 0 // Finding out the number of // perfect squares that lie // between 1 to N. count = Math.floor(Math.sqrt(N)) count = count % 2 return count } // Driver code let N = 4 // Function call if (factor(N)) document.write( "Odd" , "</br>" ) else document.write( "Even" , "</br>" ) // This code is contributed by shinjanpatra </script> |
Even
Time Complexity: O(log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!