NUMFACT - Editorial

thanx @amitrc17 got my error…

@dhruvagga : thanks…I got it. :slight_smile:

In your code, you are checking whether a[i] == 1 towards the end. But can you give me a case where it wont be equal to 1. Wont the prime numbers stored in the list make sure that the smallest number is being factorized first and then proceed to the largest??

A simple modification of Sieve of Erastothenes will also prove to be helpful. The following is what I used.

f[i] == 0 if i is prime, and if i is prime, then f[i] will have the smallest prime that will divide it.

for (int i = 2; i <= N; i++)
if (!f[i]) for (int j = i+i; j <= N; j += i) if (!f[j]) f[j] = i;

f[i] will help a lot to find all the prime divisors of a number.

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

A shorter solution with the same concept + the subtle modification of the sieve to store prime factor info.

I Even Tried Putting The Sieve Out , But Still i was only able to Solve only One Subtask !!! :’(

Any special reason for using char type of array for storing primes by setter ?

I came up with the following code, but it fails for some test cases. Can anyone help?

public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int testCases=sc.nextInt();
	int count=0;
	while(testCases-->0) {
		int numValues=sc.nextInt();
		int prod=1;
		for(int i=0;i<numValues;i++) {
			int temp=sc.nextInt();
			prod=prod*temp;
		}
		for(int i=1;i<=Math.sqrt(prod);i++) {
			if(prod%i==0) {
				if(prod/i == i) {
					count++;
				}else {
					count+=2;
				}
			}
		}
		System.out.println(count);
		count=0;
	}
	sc.close();
}

why is it that a particular test case messes up the output of the testcases that follows it? for example, with the following code ( https://www.codechef.com/viewsolution/32362756) the same sample test cases given in the question gives different output when the order of these test cases are changed. Also, the same code when run in different IDE like that in GeeksforGeeks is giving completely different answers ( for a different test set though), why is it like that? can somebody please help me out?

This is my approach.

cook your dish here

import math
import sys
def fact(x):
b=[]
k=x
while(x%2==0):
b.append(2)
x=x/2
for i in range(3,int(x)+1,2):
while(x%i==0):
b.append(i)
x=x/i
return b
for t in range(int(sys.stdin.readline())):
n=int(sys.stdin.readline())
a=[int(x) for x in sys.stdin.readline().split()]
p=1
for i in range(n):
p*=a[i]

w=[]
for i in range(n):
    r=fact(a[i])
    w=w+r
    
u=list(set(w))
g=1
for j in range(len(u)):
    g*=(w.count(u[j])+1)
    
print(g)