HackerRank Fundamentals – Leonardo’s Prime Factors

Challenge: Leonardo's Prime Factors

Subdomeniu: Fundamentals (fundamentals)

Scor cont: 10.0 / 10

Submission status: Accepted

Submission score: 1.0

Submission ID: 464719547

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/leonardo-and-prime/problem

Cerinta

Leonardo loves primes and created $q$ queries where each query takes the form of an integer, $n$. For each $n$, count the maximum number of distinct prime factors of any number in the inclusive range $[1, n]$.

**Note:** Recall that a prime number is only divisible by $1$ and itself, and $1$ is *not* a prime number.  

**Example**  
$n = 100$  

The maximum number of distinct prime factors for values less than or equal to $100$ is $3$.  One value with $3$ distinct prime factors is $30$. Another is $42$.    

**Function Description**  

Complete the *primeCount* function in the editor below.  

*primeCount* has the following parameters:  

- *int n:* the inclusive limit of the range to check  

**Returns**  

- *int:* the maximum number of distinct prime factors of any number in the inclusive range $[0 - n]$.

Input Format

The first line contains an integer, $q$, the number of queries. 	
Each of the next $q$ lines contains a single integer, $n$.

Constraints

+ $1 \le q \le 10^{5}$  
+ $1 \le n \le 10^{18}$

Cod sursa

#include <stdio.h>
#include <stdlib.h>

unsigned long long int gcd(unsigned long long int a, unsigned long long int b)
{

	while (b) {
		unsigned long long int t = b;

		b = a % b;
		a = t;
	}
	return a;
}

unsigned int max_unique_primes(unsigned long long int n)
{
	unsigned int count;
	unsigned long long int prod;
	unsigned long long int prim;

	if (n < 2)
		return 0;

	prod = 2;
	count = 1;
	for (prim = 3; prod * prim <= n; prim += 2) {
		if (gcd(prod, prim) == 1) {
			prod *= prim;
			count++;
		}
	}
	return count;
}

int main(void)
{
	unsigned int q;

	if (scanf("%u", &q) != 1)
		return EXIT_FAILURE;

	while (q--) {
		unsigned long long int n;

		if (scanf("%llu", &n) != 1)
			return EXIT_FAILURE;
		
		printf("%u\n", max_unique_primes(n));
	}
	return EXIT_SUCCESS;
}