Number of factorizations of a number.

Question

0.00/5 (No votes)

See more:

Task. Splits into different multipliers

This task is formulated very briefly.

Given a natural number N. you need to find the number of ways to represent it as a product of pairwise different factors greater than 1.

The format of the input data

The first line contains a single natural number 2 < = N < = 10^12 .

Output format

Output a single number - the number of ways to represent the number N as a product of pairwise different factors greater than 1.

Explanation for example. There are 7 different ways to represent the number 48 as a product (including a degenerate one) of pairwise different multipliers. 1: 48, 2 * 24, 3 * 16, 4 * 12, 6 *8, 2 * 3 * 8, 2 * 4 * 6.

What I have tried:

I was trying to write an algorithm and looking for a mathematical formula.

Posted 9-Oct-20 12:04pm

temchik_ggg

Updated 10-Oct-20 2:05am

v2

Add a Solution

Comments

Greg Utas 9-Oct-20 18:37pm

"Pairwise unequal"? So that rules out 2*2*12, for example?

I don't see why 2*6*4 and 4*6*2 should both be counted.

And what about 2*24?

You also said greater than 1, so 48(*1) shouldn't count.

temchik_ggg 10-Oct-20 5:20am

Sorry I made a mistake, here is the corrected question.

Task. Splits into different multipliers

This task is formulated very briefly.

Given a natural number N. you need to find the number of ways to represent it as a product of pairwise different factors greater than 1.

The format of the input data

The first line contains a single natural number 2 < = N < = 10^12 .

Output format

Output a single number - the number of ways to represent the number N as a product of pairwise different factors greater than 1.

Explanation for example. There are 7 different ways to represent the number 48 as a product (including a degenerate one) of pairwise different multipliers. 1: 48, 2 * 24, 3 * 16, 4 * 12, 6 *8, 2 * 3 * 8, 2 * 4 * 6.

Richard MacCutchan 10-Oct-20 4:17am

Start with the number divided by 2. That is the first (possible) factor. As Patrice suggest below, use the modulo function to see if that is a valid factor. Then do the same for every value below that on down to 2.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2020-10-09T13:37:00

Solution 1

As Greg spotted in comment, your example makes no sense.

In matter of integer factorization, the operation is modulo.
Modulo gives the reminder of the integer division. When modulo is 0 you got a factor.
Modulo operation - Wikipedia[^]

Posted 9-Oct-20 13:37pm

Patrice T

Comments

CPallini 10-Oct-20 1:56am

5.

Patrice T 10-Oct-20 1:59am

Thank you

temchik_ggg 10-Oct-20 5:21am

Sorry I made a mistake, here is the corrected question.

Task. Splits into different multipliers

This task is formulated very briefly.

Given a natural number N. you need to find the number of ways to represent it as a product of pairwise different factors greater than 1.

The format of the input data

The first line contains a single natural number 2 < = N < = 10^12 .

Output format

Output a single number - the number of ways to represent the number N as a product of pairwise different factors greater than 1.

Explanation for example. There are 7 different ways to represent the number 48 as a product (including a degenerate one) of pairwise different multipliers. 1: 48, 2 * 24, 3 * 16, 4 * 12, 6 *8, 2 * 3 * 8, 2 * 4 * 6.

Patrice T 10-Oct-20 5:42am

Use Improve question to update your question.
So that everyone can pay attention to this information.

temchik_ggg · Answer 2 · 2020-10-10T02:06:00

Solution 2

def algorithm(n, start=2):
    if n == 1:
        return 1
    else:
        ans = 0
        for i in range(start, n + 1):
            if n % i == 0:
                ans += algorithm(n // i, i + 1)
        return ans

num = int(input())
ans = algorithm(num)
print(ans)

Posted 10-Oct-20 2:06am

temchik_ggg

Comments

Richard MacCutchan 10-Oct-20 8:11am

Your start value should be n/2 which is the largest possible factor. And your loop should count from that value down to 2 which is the smallest.