NUMFACT confusion

general
,
1

I came across a problem, NUMFACT where the number of factors of extremely large numbers need to be calculated in under 1 second. I understood that the number needs to be factorized into its prime factors and the number of factors is equal to the product of successors (exponent + 1) of the exponents of each unique prime factor. But I am confused as to how to factorize these numbers quickly (yes, quickly, the only method I can think of trial division and I know it won’t work) and record the exponents. Are there specific data structures I should learn to handle this? Kindly suggest.

1 Like
2

This question is related to a problem from the ongoing April Challenge. So,i guess you need to wait for 9 more days for the answer.

1 Like
3

violates terms of use: ongoing contest

1 Like
4

No it isn’t. It is in the school section of codechef! http://www.codechef.com/problems/NUMFACT Codechef does not disallow problems other than contest probs being discussed

5

ok.Sorry,it was related to a question from April Challenge and so i commented that

1 Like
6

There is an editorial published, please take a look :wink:

7

I checked it out, it doesn’t mention about how to factorize integers I guess that’s a known fact but unfortunately I am kinda new to programming so I am unable to implement integer factorization :frowning: So for implementing integer factorization which algorithm/data structure should I learn? Thanks anyway

8

Ok, small hint for you - you have to factorize those Ais, each of them is up to 1.000.000 (10^6), there are 168 primes only less than 1000, so you are not dealing with such a big numbers…

9

I try submitting the solution below, get an AC only in subtask 0 and the rest, a mixture of WA and SIGSEGV. Yes, I did notice that my solution is reporting ‘NUMFACT.exe stopped working’ when I enter big numbers. About WA, I am not really sure :confused:

The idea behind this is first to create a Sieve of the 1st 168 primes which is actually a 2D array, one column containing the primes and the other containing the power of the prime against the respective prime number. Initially all the numbers in the 2nd column of the Sieve are initialized to 0. So as a prime divides one of the Ais I increment the power against the respective prime. I have copied only the primes present in the 1st column of isPrime (the sieve) into another array called Primelist so that I can increment the p easily while I perform trial division. Later I copy even the 2nd column of the isPrime so that I don’t perform unnecessary multiplications at the end.

I understand that this program is pretty inefficient time and memory wise. But I am unable to spot the discrepancy in the code which leads to WA and SIGSEGV. Kindly guide me.

and @betlista thanks for your hint. It gave me a start. :slight_smile:

http://www.codechef.com/viewsolution/3721157

1 Like
10

I’m glad I helped a bit. Another hint for you, try this test case

1
2
1009 9973
11

@betlista I finally got an AC! http://www.codechef.com/viewsolution/3722252

I really don’t know how to thank you! :smiley:

1 Like
12

It’s my pleasure to help such users as you are - that want to think about the problem, not just asking “find error in my code”. Keep this attitude, you will learn a lot :wink: Good luck.

2 Likes