583 - Prime Factors

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one »

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.... :oops:

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

but I don't want to waste anymore submission in
this problem :oops: :roll: :oops:

raymond85
New poster
Posts: 21
Joined: Tue Jul 01, 2003 9:26 am
Location: Hong Kong
Contact:

Post by 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
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

583 Why TLE

Post by 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;
}
I hate Wrong Answer!

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

583(please chack this problem)

Post by 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 != '1')
{
for(j=i;j<n;j+=i)
{
if(a=='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!='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;
}
I hate Wrong Answer!

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

583 I got accepted (need not reply)

Post by J&Jewel »

I get Accepted I just run the first loop up to sqrt(x).
I hate Wrong Answer!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

I suggest you delete some of your old post about this problem or combine it into one message.....
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by 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
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

Post by 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 :lol:
The Last Man Standing :-)

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

Post by 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 8)
The Last Man Standing :-)

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

Post by 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 :oops:
The Last Man Standing :-)

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

583

Post by Niaz Morshed »

Here is my code. Please help me ! I am totally confused about this TLE !
:oops:
[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=1;
prime[0]=0;
prime[1]=0;
for(i=2;i<=max;i++)
{
if(prime==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=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==1)
{
p=i;
break;
}
}
break;
}
}
}

c=1;
printf("%ld = ",num);
if(num<-1)
printf("-1 x ");
for(i=2;i<=k;i++)
{
if(PRIME>0)
{
for(j=0;j<PRIME;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 :-)

neo_tohin
New poster
Posts: 5
Joined: Wed Dec 31, 2003 11:24 am
Location: Bangladesh
Contact:

Easy way

Post by 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. :lol:
Live to die

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

583 Output limit exceeded ... how?

Post by 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=true;
for (i=3,k=2;k*k<=c;i+=k)
{
if (!primes[k-1] || i>=c) {k++; i=k-1;}
else primes=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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

583 why WA?

Post by 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 == 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

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

Post by 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

Post Reply

Return to “Volume 5 (500-599)”