[Solved] Leonardo's Prime Factors solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python

Algorithm

Problem Name: Mathematics - Leonardo's Prime Factors

Problem Link: https://www.hackerrank.com/challenges/leonardo-and-prime/problem?isFullScreen=true

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 <= 10⁵
1 <= n <= 10¹⁸

Sample Input

6
1
2
3
500
5000
10000000000

Sample Output

Explanation

1 is not prime and its only factor is itself.
2 has 1 prime factor, 2.
The number 3 has 1 prime factor, 3,2 has 1 and 1 has 0 prime factors.
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 & Try With Live Editor

#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);

        int q = Convert.ToInt32(Console.ReadLine().Trim());

        for (int qItr = 0; qItr < q; qItr++)
        {
            long n = Convert.ToInt64(Console.ReadLine().Trim());

            int result = Result.primeCount(n);

            textWriter.WriteLine(result);
        }

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

Copy The Code & Try With Live Editor

#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) {
    // Write your code here
        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 {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q>.forEach(qItr -> {
            try {
                long n = Long.parseLong(bufferedReader.readLine().trim());

                int result = Result.primeCount(n);

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

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Copy The Code & Try With Live Editor

#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();
});

function readLine() {
    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);

    const q = parseInt(readLine().trim(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const n = parseInt(readLine().trim(), 10);

        const result = primeCount(n);

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

    ws.end(>;
}

Copy The Code & Try With Live Editor

#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):
    # Write your code here
    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 & Try With Live Editor

Demonstration

Previous
[Solved] Army Game solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python

Next
[Solved] Connecting Towns solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python

Try With Live Editor

Category - Hacker Rank Online Judge Maniruzzaman Akash 1 year ago 913 3