{"id":"f8526817-4b1a-4ac2-83c9-bcb1895f25ac","name":"Prime Factors Using Sieve","description":"you have T numbers and for each number N you want to print all of it's prime factors.\r\n\r\nExpected complexity : 0(logn) for each query. You can do linear time preprocessing.","inputFormat":"The first line contains integer T (number of queries).\r\nNext t lines contain integer n.","outputFormat":"for each number n print all of it's prime factors.","constraints":"1<= T <= 10000\r\n1<= n <= 100000","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.ArrayList;\r\nimport java.util.Scanner;\r\n\r\nclass Main {\r\n public static void main(String args[]) {\r\n Scanner scn = new Scanner(System.in);\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n10\r\n15\r\n23\r\n93\r\n39","sampleOutput":"2 5 \r\n3 5 \r\n23 \r\n3 31 \r\n3 13 \r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"7a0addd3-431f-49f2-9130-83ccdd374ccf","name":"Prime Factors Using Sieve","slug":"prime-factors-using-sieve","type":1}],"next":{"id":"319f8b60-b521-4b74-9e86-f8673e9a6665","name":"All Factors Using Sieve","type":1,"slug":"all-factors-using-sieve"},"prev":{"id":"7bbe3fe7-4b6b-43bc-a1c8-4a53e4484e5f","name":" No Max No Min","type":1,"slug":"no-max-no-min"}}}

Prime Factors Using Sieve

you have T numbers and for each number N you want to print all of it's prime factors. Expected complexity : 0(logn) for each query. You can do linear time preprocessing.

{"id":"f8526817-4b1a-4ac2-83c9-bcb1895f25ac","name":"Prime Factors Using Sieve","description":"you have T numbers and for each number N you want to print all of it's prime factors.\r\n\r\nExpected complexity : 0(logn) for each query. You can do linear time preprocessing.","inputFormat":"The first line contains integer T (number of queries).\r\nNext t lines contain integer n.","outputFormat":"for each number n print all of it's prime factors.","constraints":"1<= T <= 10000\r\n1<= n <= 100000","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.ArrayList;\r\nimport java.util.Scanner;\r\n\r\nclass Main {\r\n public static void main(String args[]) {\r\n Scanner scn = new Scanner(System.in);\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n10\r\n15\r\n23\r\n93\r\n39","sampleOutput":"2 5 \r\n3 5 \r\n23 \r\n3 31 \r\n3 13 \r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"7a0addd3-431f-49f2-9130-83ccdd374ccf","name":"Prime Factors Using Sieve","slug":"prime-factors-using-sieve","type":1}],"next":{"id":"319f8b60-b521-4b74-9e86-f8673e9a6665","name":"All Factors Using Sieve","type":1,"slug":"all-factors-using-sieve"},"prev":{"id":"7bbe3fe7-4b6b-43bc-a1c8-4a53e4484e5f","name":" No Max No Min","type":1,"slug":"no-max-no-min"}}}
plane

Editor


Loading...

Prime Factors Using Sieve

medium

you have T numbers and for each number N you want to print all of it's prime factors. Expected complexity : 0(logn) for each query. You can do linear time preprocessing.

Constraints

1<= T <= 10000 1<= n <= 100000

Format

Input

The first line contains integer T (number of queries). Next t lines contain integer n.

Output

for each number n print all of it's prime factors.

Example

Sample Input

5 10 15 23 93 39

Sample Output

2 5 3 5 23 3 31 3 13

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode