( C programming language) given a positive integer N, what is the minimum positive integer K such that K! Is a multiple of the square of N?

Question

1.00/5 (1 vote)

See more:

Pretty new to programming, been doing some pretty basic stuff but I came across a more complicated one now, not sure how to start with it.

Task:
Given a positive integer N, what is the minimum positive integer K such that K! is a multiple of the square of N?
Note that a is a multiple of b if a=b*k for some integer k.
Moreover, note that for any positive integer M, M! is the product of all positive integers whose value is at most M.
Constraints:
1<= T <= 200000
1<= N <= 200000

Thanks a lot in advance for any tips!

What I have tried:

Nothing so far. Having problems with implementing the whole thing cuz I'm truly not sure how to do it.

[EDIT - content moved from Given a positive integer N, what is the minimum positive integer K such that K! Is a multiple of the square of N?[^] ]

Input:

The first line of input contains T, the number of test cases. The following lines describe the test cases.
Each test case consists of one line containing a single integer N.

Output:
For each test case, print a single integer which is the answer for that test case.

Sample Input

Sample Output:

Posted 9-Jan-21 4:56am

honotard

Updated 12-Jan-21 10:31am

Maciej Los

v2

Add a Solution

Comments

[no name] 9-Jan-21 11:04am

What's "T" for? And "a is a multiple of b when a=b*k" ... doh!

honotard 9-Jan-21 11:07am

The first line of input contains T which is the number of test cases, the following lines describe the test cases. Each test case consists of one line containing a single integer N.

Richard MacCutchan 9-Jan-21 11:28am

The problem is really one of mathematics. Once you have worked out how to solve that, then writing the C code should be fairly simple.

4 solutions

Solution 1

[update]

The 'Output' looks wrong to me.
Look, for instance, at the last input item, namely 24.
The output reports 48 as solution.
However,

(9!)/(24^2) = 630

so 9 looks a better fit to me.

Incidentally, considering the details of such a case could help you to solve the riddle.

[/update]

Try to solve it with pencil and paper. Then transform you findings into an algorithm. Eventually we may help you to write the C program.

Please note:

(As already noteg by Gerry) The T input variable has apparently no role in the problem.
Possibly a brute force approach would fail because of the very big numbers involved.

Posted 9-Jan-21 5:16am

CPallini

Updated 12-Jan-21 0:17am

v2

Comments

Patrice T 9-Jan-21 11:46am

+5

CPallini 9-Jan-21 11:56am

Thank you!

Maciej Los 12-Jan-21 4:42am

5ed!

CPallini 12-Jan-21 5:28am

Thank you!

Solution 3

Quote:
Nothing so far. Having problems with implementing the whole thing cuz I'm truly not sure how to do it.

You need to understand the problem and its solving.

First step, train yourself solving the problem by hand with some small N.
When your procedure works well, it is basically your algorithm.

[Update]

Quote:
I'm not understanding the definition of "K! is a multiple of the square of N" to be completely honest, so I can't really tell what is expected from me here.

Which part exactly you don't understand ?

Posted 9-Jan-21 5:40am

Patrice T

Updated 12-Jan-21 1:14am

v2

Comments

CPallini 9-Jan-21 11:57am

5.

Patrice T 9-Jan-21 11:59am

Thank you too.

Maciej Los 12-Jan-21 4:43am

5ed!

Patrice T 12-Jan-21 4:44am

Thank you

Solution 4

This is a mathematical problem as well as a programming problem.
You need to understand the maths involved and come up with a sensible approach before even attempting to program anything.
And then you must keep in mind that K! is growing rapidly with increasing K, soon to exceed the capabilities of built-in numeric types in C, so brute force approaches are to be avoided.

Hence the tip you asked for is simple: consider the prime factors of N^2 one by one.

Good luck, the rest is up to you!

:)

PS: your "sample output" doesn't fit your "sample input" but you probably knew that already.

Posted 12-Jan-21 10:31am

Luc Pattyn

Updated 12-Jan-21 10:33am

v2

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)

OriginalGriff · Accepted Answer · 2021-01-09T05:17:00

We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
When you have read that, try thinking about how you would do the task yourself instead of using a computer. When you have that working, you can start thinking about computer implementations.

( C programming language) given a positive integer N, what is the minimum positive integer K such that K! Is a multiple of the square of N?

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0

Existing Members

...or Join us