583 - Prime Factors

[deddy one]

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

[raymond85]

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.

[J&Jewel]

#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]

#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]

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

[..]

I suggest you delete some of your old post about this problem or combine it into one message.....

[mohiul alam prince]

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

[Niaz Morshed]

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

[Niaz Morshed]

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

[Niaz Morshed]

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

[Niaz Morshed]

Here is my code. Please help me ! I am totally confused about this TLE !

[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]

[neo_tohin]

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.

[Thanatos]

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]

[Morning]

[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?

[WR]

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