## 583 - Prime Factors

Moderator: Board moderators

raymond85 wrote:btw the time is quite unsatisfactory.....wonder if there's anyway to improve the speed......

when you said the time is unsatisfactory,
it make me remember the first time
I get this one accepted my time is
9.730 sec or so....

and then I tried to change a little bit of my code
and it worked faster, although still > 5 sec..

but I don't want to waste anymore submission in
this problem
deddy one
Experienced poster

Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

yea my first submission took like 4.x seconds..which is quite slow compare with others. So I wonder if there's any other improvement that can be made, so that the problem is solved in a more efficient way.
raymond85
New poster

Posts: 21
Joined: Tue Jul 01, 2003 9:26 am
Location: Hong Kong

### 583 Why TLE

#include<stdio.h>
#include<math.h>
main()
{
long x,count,s,y;
while(scanf("%ld",&x)==1)
{
if(x==0) break;
printf("%ld = ",x);
if(x<0)
{
printf("-1 x ");
x=-1*x;
}
count=2;
s=0;
y=(long) sqrt(x);
while(x!=1)
{
while(x%count==0)
{

if(x==count)
{
printf("%ld\n",x); s=1; break;
}
else printf("%ld x ",count);
x=x/count;
if(count==y && x!=4)
{
printf("%ld\n",x);
s=1; break;
}
}
if(s==1) break;
count++;
}
}
return 0;
}

J&Jewel
New poster

Posts: 50
Joined: Thu Jul 31, 2003 10:43 am

#include<stdio.h>
#include<string.h>
#include<math.h>
#define n 25000000

char a[n+100];

void prime()
{
memset(a,0,n+2);
long i,j;
a[0]='1';a[1]='1';
for(i=2; i <= sqrt(n);++i)
{
if(a[i] != '1')
{
for(j=i;j<n;j+=i)
{
if(a[i]=='1'){}
else a[j+i]='1';
}
}
}
}
int main()
{
prime();
long m,sum,temp,i;
//freopen ("g:\\583.txt","r",stdin);
while(scanf("%ld",&m)==1)
{
temp=0;
if(m == 0)break;
printf("%ld = ",m);
if(m<0)
{
printf("-1 x ");
m=-1*m;
}
if(a[m]!='1')
printf("%ld",m);
else
{
for(i=2;i<=m;i++)
{
if(a[i]!='1')
{
while(1)
{
sum=m%i;
if(sum==0)
{
printf("%ld",i);
}
else break;
temp=m/i;
if(temp==1)break;
else m=temp;
if(sum==0)printf(" x ");
}
}
if(temp==1)break;
}
}
printf("\n");
}
return 0;
}

J&Jewel
New poster

Posts: 50
Joined: Thu Jul 31, 2003 10:43 am

### 583 I got accepted (need not reply)

I get Accepted I just run the first loop up to sqrt(x).

J&Jewel
New poster

Posts: 50
Joined: Thu Jul 31, 2003 10:43 am

My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

what u have done i don't understand

but it will be help to u (c++)

prime()
{
while((c%2==0))
{
c=c/2;
printf("2");
}
i=3;
while(sqrt(c)/i==0)
{
printf("%ld",i);
c=c/i;
i=i+2;
}
if(c>1)printf("%ld",c);

prince
10-11-2003

mohiul alam prince
Experienced poster

Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

I dont know the reason for TLE but for this in put <2147483647> your program does not give any out put. WHY ? At first try to fix this problem. Hopefully you can find the TLE reason soon. I will try to reply again. I will look at ur code carefully later.
Niaz
The Last Man Standing
Niaz Morshed
New poster

Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.

I got it . Your code can not ganerate big PRIMES. Use sieve methods to generate PRIMES. If u do not know the method, tell me... i will send u my function which can generate big primes.
Niaz
The Last Man Standing
Niaz Morshed
New poster

Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.

Hi raymond85 !
I tried to solve this problem and faced the same problem that u faced. I use sieve method to find the primes from 2 to 20000000. then for bigger prime i use 'sqrt' method. My code can run quite nice in my PC for large input. such as (2^31)-1 but i got TLE. Why ? can u help me to solve this problem ? I will wait for ur reply. Thanks in advance.
Niaz
The Last Man Standing
Niaz Morshed
New poster

Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.

### 583

[cpp]#include<stdio.h>
#include<math.h>
#define max 2000000
char prime[max+10];
long PRIME[90000];
/*int isprime(long n)
{
long i;
for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
return 0;
}
return 1;
}*/
void find_prime()
{
long i,j;
for(i=0;i<=max;i++)
prime[i]=1;
prime[0]=0;
prime[1]=0;
for(i=2;i<=max;i++)
{
if(prime[i]==1)
{
for(j=i+i;j<=max;j=j+i)
{
if(j>max)
break;
prime[j]=0;
}
}
}
}

int main()
{
long num3,num,num2,k,c,i,j,p,m,n;
find_prime();
while(1)
{
scanf("%ld",&num);

if(num==0)
break;
if(num<0)
num2=num*-1;
else
num2=num;

num3=num2;
k=sqrt(num2);

for(i=0;i<=k;i++)
PRIME[i]=0;

p=2;
while(p<=k)
{
while(1)
{
m=num2%p;
n=num2/p;
if(m==0)
{
PRIME[p]++;
num2=n;
}
else
{
for(i=p+1;;i++)
{
if(prime[i]==1)
{
p=i;
break;
}
}
break;
}
}
}

c=1;
printf("%ld = ",num);
if(num<-1)
printf("-1 x ");
for(i=2;i<=k;i++)
{
if(PRIME[i]>0)
{
for(j=0;j<PRIME[i];j++)
{
if(c==1)
{
c=0;
printf("%ld ",i);
}
else
{
printf("x %ld ",i);
}
}
}
}
if(num==-1)
printf("-");
/*if(num==1)
printf("1");*/
if(num2>=sqrt(num3))
{
if(c==0)
printf("x %ld",num2);
else
printf("%ld",num2);
}
printf("\n");
}
return 0;
}[/cpp]
The Last Man Standing
Niaz Morshed
New poster

Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.

### Easy way

I think your code is very big one. And you are generated all primes.
Check the way that i generate the prime factor of 24

24 / 2 = 12
12 / 2 = 6
6 / 2 = 3
3 / 3 = 1
so the prime factors are 24 = 2 * 2 * 2 * 3.

Ha Ha easy way isn't it.
Live to die
neo_tohin
New poster

Posts: 5
Joined: Wed Dec 31, 2003 11:24 am

### 583 Output limit exceeded ... how?

Hey guys.

I don't know why I'm getting OLE from my code. I don't seem to encounter any infinite loops whatsoever...

Also what happens if you put in '1' ? Is it just 1 = 1?

Help appreciated

[cpp]#include <stdio.h>
#include <math.h>

bool *primes;
long c=46341;

long nextprime(long i)
{
for (i++;i<=c;i++)
if (primes[i-1]) return i;
return -1;
}

bool isprime(long long n) {
if (n==2 || n==3) return true;
if (n==1) return false;
for (long i=2;i<=(long)sqrt(n); i=nextprime(i))
if (n%i==0) return false;
return true;
}

int main()
{
long long x;
int i,k;
primes=new bool[c];
primes[0]=false; primes[1]=primes[2]=true;
for (i=3;i<c;i++) primes[i]=true;
for (i=3,k=2;k*k<=c;i+=k)
{
if (!primes[k-1] || i>=c) {k++; i=k-1;}
else primes[i]=false;
}

long counter;
bool y;

while (scanf("%lld",&x)==1)
{
if (x==0) break;
counter=2;
if (x<0) {printf("%lld = -1 x ",x); x*=-1;}
else printf("%lld = ",x);
if (x==1 || isprime(x)) { printf("%lld\n",x); continue; }
for (y=false;;counter=nextprime(counter))
{
if (counter*counter>x) { printf("%lld\n",x); break; }
while (x%counter==0) {
x/=counter;
if (x==1) {printf("%ld\n",counter); y=true; break;}
else printf("%ld x ",counter);
}
if (y) break;
}
}
delete [] primes;

return 0;
}

[/cpp]
Thanatos
New poster

Posts: 5
Joined: Tue Mar 09, 2004 11:14 am

### 583 why WA?

[cpp]
#include <iostream>
#include <cmath>
using namespace std;
long long primes[4800];
int point;
int prime(long long n)
{
for(int i = 0;i < point;i++)
{
if (n % primes[i] == 0)
{
return 0;
}
}
return 1;
}
int output(long long n)
{
int firstFlag = 1;
if (n == -1 || n == 0 || n == 1)
{
cout << n << " = " << n << endl;
return 1;
}
if (n < 0)
{
cout << n << " = -1";
n = n * -1;
firstFlag = 0;
}
else
{
cout << n << " =";
}
int p = 0;
while(n != 1)
{
while(n % primes[p] == 0)
{
if(firstFlag)
{
cout << ' ' << primes[p];
firstFlag = 0;
}
else {cout << " x " << primes[p];}
n /= primes[p];
}
p++;
if(p > 4791)
{
if(firstFlag)
{
cout << ' ' << n;
firstFlag = 0;
}
else {cout << " x " << n;}
break;
}

}
cout << endl;
}
int main()
{
long long n;
primes[0] = 2;
primes[1] = 3;
point = 2;
for(long long i = 5;i <= 46340;i += 2)
{
if(prime(i))
{
primes[point++] = i;
}
}
while(cin >> n)
{
if(n == 0) break;
output(n);
}
return 0;
}
[/cpp]

is there someone who can give me some input/output case?
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius
Morning
Experienced poster

Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

49 = 7 x 7
1073741824 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2
1 = 1
-1 = -1
64 = 2 x 2 x 2 x 2 x 2 x 2
-190 = -1 x 2 x 5 x 19
-191 = -1 x 191
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
-193 = -1 x 193
-194 = -1 x 2 x 97
195 = 3 x 5 x 13
196 = 2 x 2 x 7 x 7
197 = 197
198 = 2 x 3 x 3 x 11
199 = 199
200 = 2 x 2 x 2 x 5 x 5
2147483647 = 2147483647
2147483646 = 2 x 3 x 3 x 7 x 11 x 31 x 151 x 331
-2147483647 = -1 x 2147483647
-2147483646 = -1 x 2 x 3 x 3 x 7 x 11 x 31 x 151 x 331
WR
Experienced poster

Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

PreviousNext