Soluție HackerRank pentru Leonardo's Prime Factors, subdomeniul Fundamentals, în C++14. Include cerința formatată, exemple, explicația pașilor și cod…
- Problemă: Leonardo's Prime Factors
- Domeniu: Fundamentals
- Limbaj: C++14
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
Cerință
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 ≤ q ≤ 10^5
+ 1 ≤ n ≤ 10^18
Cod sursă
#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;
}