PFACT - Prime Factors

no tags 

Bhelu is very fond of prime numbers as well as factors of a number. So, he wishes to find all the prime factors of a number...

Your task is very simple. You just have to print all the prime factors in increasing order of all the numbers upto 10^5.

Note: Bhelu is smart and he knows that 1 is not a prime. So start printing prime factors of n such that (2 <= n <= 10^5).

Input

There is no input....

Output

10^ 5 - 1 lines containing prime factors of numbers, one line for each number in the following format:

<number>: <all the prime factors>

Example

Output:
2: 2
3: 3
4: 2
5: 5
6: 2 3
.
.
.
.
100000: 2 5

hide comments
jshreyash: 2021-02-11 11:30:10

Did Anyone got AC in Python

[NG]: I did, but it's barely possible here. I recommend you get your PRIME1 solution working and experiment with problems where the limits are more reasonable.

Last edit: 2021-02-11 23:06:59
harshitnsharma: 2021-02-09 12:56:14

did anybody got this AC in Java ????

shawon10: 2017-06-20 09:12:04

What a horrible problem!!! Same solution in C++ is getting time limit exceed but in C it is accepted .

:D: 2013-02-15 22:09:18

Well I moved it to tutorial and somebody moved it back. I would really nicely advice against that :)

abdelkarim: 2013-02-15 22:05:32

tutorial problem !

:D: 2013-02-15 21:15:52

It's a tutorial material. That said it's a very good tutorial, since a pretty naive prime searching algorithm passes. So it's a good starting point for users new to number theory.

Alex Anderson: 2013-02-15 21:15:52

I think this problem is similar to this one: http://www.spoj.com/problems/FACTCG2/


Added by:c[R]@zY f[R]0G
Date:2013-02-15
Time limit:0.100s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64