SPOJ.com - Problem PFACT

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 up to 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:

Example

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

Submit solution!

hide comments



	[Lakshman]: 2024-01-25 00:35:01 @sahilkrsinha Actually this is an easy problem, only challenge you have here is to write very fast. You can check for fast IO in cpp. O(N log N) is more than enough. https://www.geeksforgeeks.org/fast-io-for-competitive-programming/ Last edit: 2024-01-25 00:38:12
	sahilkrsinha: 2024-01-17 23:31:31 guys i tried a lot to solve using sieve but could not do it , every time there is TLE . I am kind a new here ,can anyone help me out, how to solve this problem ? is there a way to see the solution ? Last edit: 2024-01-17 23:32:21
	ritiksh1607: 2021-02-27 07:15:01 @harshitnsharma i am also getting same pblm in java , i got tle , do you resolved it
	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/

Submit solution!

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