## Algorithm

Problem Name: Mathematics - Leonardo's Prime Factors

In this HackerRank in Mathematics - Leonardo's Prime Factors solutions,

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 <= 105
• 1 <= n <= 1018

Sample Input

6
1
2
3
500
5000
10000000000


Sample Output

0
1
1
4
5
10


Explanation

1. 1 is not prime and its only factor is itself.
2. 2 has 1 prime factor, 2.
3. The number 3 has 1 prime factor, 3,2 has 1 and 1 has 0 prime factors.
4. The product of the first four primes is 2 * 3 * 5 * 7 = 210. While higher value primes may be a factor of some numbers, there will never be more than 4 distinct prime factors for a number in this range.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);

/*
* Complete the 'primeCount' function below.
*
* The function is expected to return an INTEGER.
* The function accepts LONG_INTEGER n as parameter.
*/

int primeCount(long n) {

if (n == 1) return 0;

vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
unsigned long long m = 1;
int cnt = 0;
for (int prime : primes){
m *= (unsigned long long)prime;

if (m > n) break;
if (m == n){
cnt++;
break;
}
cnt++;
}
return cnt;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

string q_temp;
getline(cin, q_temp);

int q = stoi(ltrim(rtrim(q_temp)));

for (int q_itr = 0; q_itr  <  q; q_itr++) {
string n_temp;
getline(cin, n_temp);

long n = stol(ltrim(rtrim(n_temp)));

int result = primeCount(n);

fout << result << "\n";
}

fout.close();

return 0;
}

string ltrim(const string &str) {
string s(str);

s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
);

return s;
}

string rtrim(const string &str) {
string s(str);

s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
s.end()
);

return s;
}

Copy The Code &

### #2 Code Example with C# Programming

Code - C# Programming


using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

/*
* Complete the 'primeCount' function below.
*
* The function is expected to return an INTEGER.
* The function accepts LONG_INTEGER n as parameter.
*/

public static int primeCount(long n)
{
ulong productOfPrimes=1;
ulong[] firstPrimes= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53};

for (int i = 0 ; i  < firstPrimes.Length; i++){
productOfPrimes*=firstPrimes[i];

if(productOfPrimes > (ulong)n)
return i;
if(productOfPrimes == (ulong)n)
return i+1;
}
return 0;
}

}

class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

for (int qItr = 0; qItr < q; qItr++)
{

int result = Result.primeCount(n);

textWriter.WriteLine(result);
}

textWriter.Flush();
textWriter.Close(>;
}
}

Copy The Code &

### #3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

/*
* Complete the 'primeCount' function below.
*
* The function is expected to return an INTEGER.
* The function accepts LONG_INTEGER n as parameter.
*/

public static int primeCount(long n) {
if(n==1){
return 0;
}else if(n<=5>{
return 1;
}else if(n  >= Long.parseLong("614889782588491410")){
return 15;
}else{
List < Integer> prime=new ArrayList<>(Arrays.asList( 2,3, 5, 7, 11, 13, 17, 19, 23,                                                 29, 31, 37, 41, 43, 47, 53, 59,61, 67));
long l=1;
long h=1;
for(int i=0;i <  prime.size()-1; i++){
l=h;
h *=Long.parseLong(Integer.toString(prime.get(i)) );
if(n >= l && n < h){
return i;
}
}
}
return -1;
}

}

public class Solution {
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

IntStream.range(0, q>.forEach(qItr -> {
try {

int result = Result.primeCount(n);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});

bufferedWriter.close();
}
}

Copy The Code &

### #4 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});

process.stdin.on('end', function() {
inputString = inputString.split('\n');

main();
});

return inputString[currentLine++];
}

/*
* Complete the 'primeCount' function below.
*
* The function is expected to return an INTEGER.
* The function accepts LONG_INTEGER n as parameter.
*/

function primeCount(n) {
if(n<2) return 0;
if((n+"").length==19> return 15;
let mulPrimes = [
2,
6,
30,
210,
2310,
30030,
510510,
9699690,
223092870,
6469693230,
200560490130,
7420738134810,
304250263527210,
13082761331670030,
"614889782588491410"];
let i = 0;
while(n>=mulPrimes[i] && i < 14) i++;
if(i==14){
if(n+"">=mulPrimes[14]) i++;
}
return i;
}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

for (let qItr = 0; qItr < q; qItr++) {

const result = primeCount(n);

ws.write(result + '\n');
}

ws.end(>;
}

Copy The Code &

### #5 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'primeCount' function below.
#
# The function is expected to return an INTEGER.
# The function accepts LONG_INTEGER n as parameter.
#

def primeCount(n):
x = 0
s = 1
for i in range(2, n+1):
flag = True
for j in range(2, int(math.sqrt(i))+1):
if i % j == 0:
flag = False
break
if flag:
s *= i
if s > n:
break
x += 1
return x

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

q = int(input().strip())

for q_itr in range(q):
n = int(input().strip())

result = primeCount(n)

fptr.write(str(result) + '\n')

fptr.close()

Copy The Code &