Either you can use a sieve to extend your primes array or just put more primes in the primes array.
here’s a sample code for sieve.
http://ideone.com/arhRSv
1 Like
@shasha1s2 wen u update ‘other’ array to count prime u do not account for the fact that the prime number being counted may be the same…in other words, the value of other[i] (according to your code) will never be more than 1…going by that the test case
5
999983 999983 999983 999983 999983
will give 32 as per your code, while ans is 6.
2 Likes
It gives a TLE when i use the function ‘prime’ to find the prime factorisation of the number.Can someone please tell me where i went wrong? Thanks in advance.
Here is the link to my code : kgzICq - Online C++ Compiler & Debugging Tool - Ideone.com
@roshi…it will most certainly give a TLE as the time complexity is very high!!!
try using Sieve of Eratosthenes…see the time difference…Naive approach…seive!!!
1 Like
What is wrong in my code??
It gives correct answers to all the numbers with which I have checked. 
@shubham26
if you look at the constraints .They are :-
N<=10
Ai<=1000000
and as in your code you multiply each Ai to get a number which is product of all of them.
Suppose if all the numbers are 10^6 and N=10 and they are multiplied N times,the number becomes (10^6)^10=10^60 which is far beyond the range of long(range of the order 10^9)( (even its far away from long long(range of the order 10^18)).
1 Like
In the setter’s solution what is the use of this code fragment
if(a[i]!=1)
{
if(m.find(a[i])!=m.end())
m[a[i]]++;
else
m.insert(MP(a[i],1));
from line 85 to 90
I put that in comments and ran the program and it gave the correct o/p for test cases. I don’t understand it’s use. After dividing with all the prime numbers shouldn’t a[i] necessarily be 1.
1 Like
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
if(t>=1 && t<=100)
{
while(t–)
{
int n;
scanf("%d",&n);
if(n>=1&&n<=10)
{
long int a, total=1;
while(n–)
{
scanf("%ld",&a);
if(a>=2&&a<=1000000)
total*=a;
}
int count=0;
for(int i=1;i<=total;i++)
{
if(total%i==0)
count++;
}
printf("%d\n",count);
}
}
}
return 0;
}
why time limit exist???
Can anyone provide critical input. My solutions keeps getting WA, however, when comparing to AC code gives same output.
from sys import stdin
from collections import Counter
from math import sqrt,ceil
def primes(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
def factor(n):
upper = n
i = 0
while sieve[i] <= ceil(sqrt(upper)):
while n%sieve[i]==0:
n/=sieve[i]
if sieve[i] not in factors:
factors[sieve[i]]=0
factors[sieve[i]]+=1
i+=1
if(n>1):
if upper not in factors:
factors[upper]=0
factors[upper]+=1
sieve = primes(10000)
factors = {}
def solve():
N = int(stdin.readline())
numbers = map(int,stdin.readline().split())
#print([i for i in numbers])
factors.clear()
for num in numbers:
factor(num)
tot = 1
for num in factors:
#print("fac",num,factors[num])
tot *= (factors[num]+1)
print tot
def main():
tc = int(stdin.readline())
for i in range(1,tc+1):
solve()
if __name__=="__main__":
main()whats the problem wid following ? i got a WA
#include<stdio.h>
#include<math.h>
int primes[1000000];
int a[1000000];
void gen_primes(int n)
{
int i,j;
for(i=0;i<n;i++)
primes[i]=1;
for(i=2;i<=(int)sqrt(n);i++)
{
if(primes[i])
{
for(j=i;j*i<n;j++)
{
primes[i*j]=0;
}
}
}
}
main()
{
int t,n,i;
long long int p,x;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<(int)sqrt(n);i++)
{
a[i]=0;
}
gen_primes(n);
while(n--)
{
scanf("%lld",&x);
for(i=2;i<=(int)sqrt(n);i++)
{
if(primes[i])
{
if(x%i==0)
{
a[i]=a[i]+(long long int)((double)log(x)/(double)log(i));
}
}
}
}
p=1;
for(i=2;i<=(int)sqrt(n);i++)
{
if(a[i])
{
p=p*(a[i]+1);
}
}
printf("%lld\n",p);
}
return 0;
}my code is running fine on the first time… but in second test case giving erronous output… please help…
#include<stdio.h>
int freq[1000000];
int sum;
void count(long long int x)
{
int i;
for(i=2;;i++)
{
while(x%i==0)
{
freq[i]++;
x=x/i;
sum++;
}
if(x==1)
break;
}
}
int main(void)
{
int t,n,p,y,i;
long long int x;
scanf("%d",&t);
while(t--)
{
p=1;
y=0;
sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
freq[i]=0;
while(n--)
{
scanf("%lld",&x);
count(x);
}
for(i=0;;i++)
{
if(freq[i]!=0)
{
p=p*(freq[i]+1);
y=y+freq[i];
if(y==sum)
break;
}
}
printf("%d\n",p);
}
return 0;
}Where Am i Going Wrong , Its Always SIGSEV and TLE on my Submission :’( , Plz help me Fast i Need to Brace up For IOI
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(long long int *primes,long long int *n )
{
long long int *z = (long long int *)calloc(1001,sizeof
(long long int));
while(*n>1)
{
for(long long int i=0;i<168;i++)
{
if(*n%primes[i]==0){z[i]++;*n= *n/primes[i];i--;}
}
}
long long int prod=1;
for(long long int k=0;k<168;k++)if(z[k]!=0)prod*=(z[k]+1);
printf("%lld \n",prod);
//for(long int i=0;i<n&&primes[i]!=0;i++)printf("%ld \n",primes[i]);
}
int main()
{
long long int *primes;
primes = (long long int *)calloc(1001,sizeof(long long int));
primes[0]=2;
primes[1]=3;
long long int index=2;
for(long long int z=5;z<=1001;z+=2)
{
long long int fact=0;
for(long long int i=0;i<1001&&primes[i]!=0;i++)
{
if(z%primes[i]==0){fact++;break;};
}
if (fact==0)
{
primes[index]=z;
index++;
}
}
long long int t;
scanf("%lld",&t);
while(t--){
long long int n,prod=1,temp;
scanf("%lld",&n);
for(long long int i=0;i<n;i++){scanf("%lld",&temp);prod*=temp;}
solve(primes,&prod);
}
}Hey whats wrong in my code here?
program FACTORS;
uses Math;
var
t,n,num,product:longint;
function factors(fact:longint):longint;
var
no:longint = 0;
x:longint;
begin
for x := 1 to floor(sqrt(fact)) do
begin
if fact mod x = 0 then
begin
if x*x = fact then inc(no,1)
else inc(no,2);
end;
end;
factors := no;
end;
begin
readln(t);
while t <> 0 do
begin
readln(n);
product := 1;
while n <> 0 do
begin
read(num);
product := product * num;
dec(n);
end;
writeln(factors(product));
dec(t);
end;
end.
I am getting runtime error NZEC.
I have been trying to debug my code for so long still not able to figure out why it is giving a WA for the basic cases. Please if anyone could tell me where am I going wrong?
This is the link to my solution.
https://www.codechef.com/submit/complete/8669014
nice explanation.
I used sieve of eratosthenes to get all prime factors of number
https://www.codechef.com/viewsolution/14084014
WHY IS THIS SOLUTION GETTING A WA ON LAST CASE PLZ HELP!!
it works… I have used “other” array for those primes
Can u provide any testcase where it fails…
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??