Given a number N, find the first triangular number whose number of divisors exceeds N. Triangular numbers are sums of natural numbers, i. e., of the form x*(x+1)/2. First few triangular numbers are 1, 3, 6, 10, 15, 21, 28, …
Examples:
Input: N = 2
Output: 6
6 is the first triangular number with more than 2 factors.
Input: N = 4
Output: 28
A naive solution is to iterate for every triangular number and count the number of divisors using the Sieve method. At any moment if the number of divisors exceeds the given number N, then we get our answer. If the triangular number which has more than N divisors is X, then the time complexity will be O(X * sqrt(X)) as pre-processing of primes is not possible in case of larger triangular numbers. The naive solution is important to understand in order to solve the problem more efficiently.
An efficient solution will be to use the fact that the triangular number’s formula is x*(x+1)/2. The property that we will use is that k and k+1 are coprimes. We know that two co-primes have a distinct set of prime factors. There will be two cases when X is even and odd.
- When X is even, then X/2 and (X+1) will be considered as two numbers whose prime factorisation is to be find out.
- When X is odd, then X and (X+1)/2 will be considered as two numbers whose prime factorisation is to be find out.
Hence the problem has been reduced to the just finding out prime factorization of smaller numbers, which reduces the time complexity significantly. We can reuse the prime factorization for x+1 in the subsequent iterations, and thus factorizing one number in each iteration will do. Iterating till the number of divisors exceeds N and considering the case of even and odd will give us the answer.
Below is the implementation of the above approach.
C++
// C++ efficient program for counting the// number of numbers <=N having exactly// 9 divisors#include <bits/stdc++.h>using namespace std;const int MAX = 100000;// sieve method for prime calculationbool prime[MAX + 1];// Function to mark the primesvoid sieve(){ memset(prime, true, sizeof(prime)); // mark the primes for (int p = 2; p * p < MAX; p++) if (prime[p] == true) // mark the factors of prime as non prime for (int i = p * 2; i < MAX; i += p) prime[i] = false;}// Function for finding no. of divisorsint divCount(int n){ // Traversing through all prime numbers int total = 1; for (int p = 2; p <= n; p++) { if (prime[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization int count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } return total;}// Function to find the first triangular numberint findNumber(int n){ if (n == 1) return 3; // initial number int i = 2; // initial count of divisors int count = 0; // prestore the value int second = 1; int first = 1; // iterate till we get the first triangular number while (count <= n) { // even if (i % 2 == 0) { // function call to count divisors first = divCount(i + 1); // multiply with previous value count = first * second; } // odd step else { // function call to count divisors second = divCount((i + 1) / 2); // multiply with previous value count = first * second; } i++; } return i * (i - 1) / 2;}// Driver Codeint main(){ int n = 4; // Call the sieve function for prime sieve(); cout << findNumber(n); return 0;} |
Java
// Java efficient program for counting the // number of numbers <=N having exactly // 9 divisors public class GFG { final static int MAX = 100000; // sieve method for prime calculation static boolean prime[] = new boolean [MAX + 1]; // Function to mark the primes static void sieve() { for(int i = 0 ; i <= MAX ; i++) prime[i] = true; // mark the primes for (int p = 2; p * p < MAX; p++) if (prime[p] == true) // mark the factors of prime as non prime for (int i = p * 2; i < MAX; i += p) prime[i] = false; } // Function for finding no. of divisors static int divCount(int n) { // Traversing through all prime numbers int total = 1; for (int p = 2; p <= n; p++) { if (prime[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization int count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } return total; } // Function to find the first triangular number static int findNumber(int n) { if (n == 1) return 3; // initial number int i = 2; // initial count of divisors int count = 0; // prestore the value int second = 1; int first = 1; // iterate till we get the first triangular number while (count <= n) { // even if (i % 2 == 0) { // function call to count divisors first = divCount(i + 1); // multiply with previous value count = first * second; } // odd step else { // function call to count divisors second = divCount((i + 1) / 2); // multiply with previous value count = first * second; } i++; } return i * (i - 1) / 2; } public static void main(String args[]) { int n = 4; // Call the sieve function for prime sieve(); System.out.println(findNumber(n)); } // This Code is contributed by ANKITRAI1} |
Python3
# Python 3 efficient program for counting the# number of numbers <=N having exactly# 9 divisorsfrom math import sqrtMAX = 100000prime = [ True for i in range(MAX + 1)]# Function to mark the primesdef sieve(): # mark the primes k = int(sqrt(MAX)) for p in range(2,k,1): if (prime[p] == True): # mark the factors of prime as non prime for i in range(p * 2,MAX,p): prime[i] = False# Function for finding no. of divisorsdef divCount(n): # Traversing through all prime numbers total = 1 for p in range(2,n+1,1): if (prime[p]): # calculate number of divisor # with formula total div = # (p1+1) * (p2+1) *.....* (pn+1) # where n = (a1^p1)*(a2^p2).... # *(an^pn) ai being prime divisor # for n and pi are their respective # power in factorization count = 0 if (n % p == 0): while (n % p == 0): n = n / p count += 1 total = total * (count + 1) return total# Function to find the first triangular numberdef findNumber(n): if (n == 1): return 3 # initial number i = 2 # initial count of divisors count = 0 # prestore the value second = 1 first = 1 # iterate till we get the first triangular number while (count <= n): # even if (i % 2 == 0): # function call to count divisors first = divCount(i + 1) # multiply with previous value count = first * second # odd step else: # function call to count divisors second = divCount(int((i + 1) / 2)) # multiply with previous value count = first * second i += 1 return i * (i - 1) / 2# Driver Codeif __name__ == '__main__': n = 4 # Call the sieve function for prime sieve() print(int(findNumber(n)))# This code is contributed by # Surendra_Gangwar |
C#
// C# efficient program for counting the // number of numbers <=N having exactly // 9 divisors using System;public class GFG { static int MAX = 100000; // sieve method for prime calculation static bool[] prime = new bool [MAX + 1]; // Function to mark the primes static void sieve() { for(int i = 0 ; i <= MAX ; i++) prime[i] = true; // mark the primes for (int p = 2; p * p < MAX; p++) if (prime[p] == true) // mark the factors of prime as non prime for (int i = p * 2; i < MAX; i += p) prime[i] = false; } // Function for finding no. of divisors static int divCount(int n) { // Traversing through all prime numbers int total = 1; for (int p = 2; p <= n; p++) { if (prime[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization int count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } return total; } // Function to find the first triangular number static int findNumber(int n) { if (n == 1) return 3; // initial number int i = 2; // initial count of divisors int count = 0; // prestore the value int second = 1; int first = 1; // iterate till we get the first triangular number while (count <= n) { // even if (i % 2 == 0) { // function call to count divisors first = divCount(i + 1); // multiply with previous value count = first * second; } // odd step else { // function call to count divisors second = divCount((i + 1) / 2); // multiply with previous value count = first * second; } i++; } return i * (i - 1) / 2; } public static void Main() { int n = 4; // Call the sieve function for prime sieve(); Console.Write(findNumber(n)); } } |
PHP
<?php// PHP efficient program for counting the// number of numbers <=N having exactly// 9 divisors$MAX = 10000;// sieve method for $prime calculation$prime = array_fill(0, $MAX + 1, true);// Function to mark the primesfunction sieve(){ global $prime; global $MAX; // mark the primes for ($p = 2; $p * $p < $MAX; $p++) if ($prime[$p] == true) // mark the factors of prime // as non prime for ($i = $p * 2; $i < $MAX; $i += $p) $prime[$i] = false;}// Function for finding no. of divisorsfunction divCount($n){ global $prime; // Traversing through all prime numbers $total = 1; for ($p = 2; $p <= $n; $p++) { if ($prime[$p]) { // calculate number of divisor // with formula $total div = // (p1+1) * (p2+1) *.....* (pn+1) // where $n = (a1^p1)*(a2^p2).... // *(an^pn) ai being $prime divisor // for $n and pi are their respective // power in factorization $count = 0; if ($n % $p == 0) { while ($n % $p == 0) { $n = $n / $p; $count++; } $total = $total * ($count + 1); } } } return $total;}// Function to find the first// triangular numberfunction findNumber($n){ if ($n == 1) return 3; // initial number $i = 2; // initial count of divisors $count = 0; // prestore the value $second = 1; $first = 1; // iterate till we get the // first triangular number while ($count <= $n) { // even if ($i % 2 == 0) { // function call to $count divisors $first = divCount($i + 1); // multiply with previous value $count = $first * $second; } // odd step else { // function call to $count divisors $second = divCount(($i + 1) / 2); // multiply with previous value $count = $first * $second; } $i++; } return $i * ($i - 1) / 2;}// Driver Code$n = 4;// Call the sieve function for primesieve();echo findNumber($n);// This code is contributed by ihritik?> |
Javascript
<script>// javascript efficient program for counting the // number of numbers <=N having exactly // 9 divisors const MAX = 100000;// sieve method for prime calculationlet prime = new Array(MAX + 1).fill(0); // Function to mark the primes function sieve() { for (i = 0; i <= MAX; i++) prime[i] = true; // mark the primes for (p = 2; p * p < MAX; p++) if (prime[p] == true) // mark the factors of prime as non prime for (i = p * 2; i < MAX; i += p) prime[i] = false; } // Function for finding no. of divisors function divCount(n) { // Traversing through all prime numbers var total = 1; for (p = 2; p <= n; p++) { if (prime[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization var count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } return total; } // Function to find the first triangular number function findNumber(n) { if (n == 1) return 3; // initial number var i = 2; // initial count of divisors var count = 0; // prestore the value var second = 1; var first = 1; // iterate till we get the first triangular number while (count <= n) { // even if (i % 2 == 0) { // function call to count divisors first = divCount(i + 1); // multiply with previous value count = first * second; } // odd step else { // function call to count divisors second = divCount((i + 1) / 2); // multiply with previous value count = first * second; } i++; } return i * (i - 1) / 2; } var n = 4; // Call the sieve function for prime sieve(); document.write(findNumber(n));// This code contributed by Rajput-Ji </script> |
Output
28
Time Complexity: O(N*logN),
- Sieve of eratosthenes will cost O(N*log(logN)) time, but
- we are using nested loops where the outer loop traverses N times and the inner loop traverses logN times as in every traversal we are decrementing by floor division of factor of n.
Auxiliary Space: O(105), as we are using extra space for primer array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
