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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Code: Select all

``````long bil_prima[10000]={prime number between 1-50000}
``````
Does that compile on your computer?

As a side: I wouldn't mix integer and floating point types, because you might introduce rounding errors.

Code: Select all

``for(long  j=2; j<=sqrt(angka);j++)``
You can use

Code: Select all

``for(long  j=2; j*j<=angka;j++) ``
without loss of precision.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Deny Sutani
New poster
Posts: 6
Joined: Fri Jun 01, 2007 7:20 am
At the first time, I make a function to generate all prime between 1-50000. I think if i remake my code like that, it will increase the process.

In my real code it's written like this

long bil_prima[10000]={
2, 3, 5, 7, 11, 13, 17, 19,..., 49853, 49871, 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957, 49991, 49993, 49999};

... = prime number too.

I think it will br too long write it all here.

And thanx for your advice. I can't believe that the first rank reply my post. So glad.

And I'm sorry if my posting has to many error. I'm not sufficient enough in English.

Deny Sutani
New poster
Posts: 6
Joined: Fri Jun 01, 2007 7:20 am
I try to change my code. It produces RE(Signal

Code: Select all

``````#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define max 50000
long bil_prima[5133];

bool prime[max+1];

void prima()
{
int i,j,x=0;
int limit = (int) sqrt(max)+1;
for (i=1;i<=max;i++) prime[i] = i&1;
prime[0] = prime[1] = false;
prime[2] = true;
for (i=3 ; i <= limit ; i+=2)
{
if (prime[i])
for ( j = i*i ; j<=max;j+=i)
prime[j] = false;
}
for(i=0;i<max;i++)
{
if(prime[i]==true)
{
bil_prima[x] = i;
x++;
}
}

}

int main()
{

freopen("input.in","r",stdin);
freopen("output.out","w",stdout);

long angka,temp, x;
prima();
while(scanf("%ld",&angka) && angka !=0)
{

printf("%ld = ",angka);
x = 0;
if(angka < -1)
{
printf("-1 x ");
angka = angka * -1;
}

while(angka>1)
{

if(bil_prima[x]*bil_prima[x] > angka)
{
printf("%ld\n",angka);
break;
}
if(angka%bil_prima[x]==0)
{
printf("%ld ", bil_prima[x]);
angka/=bil_prima[x];
if (angka > 1) printf("x ");
}
else bil_prima[x++];
}
}
return 0;
}
``````
Somebody help me?

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

### 583 RTE,help needed

i am getting RTE. plz explain why. for what limit i will have to generate prime?
here is my code

Code: Select all

``````AC

``````
Last edited by Fuad Hassan EWU on Sun Aug 05, 2007 12:48 am, edited 1 time in total.
Eagle er moto daana meley urbo

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:
thanx to all.

Code: Select all

``````  Accepted
``````
Last edited by newton on Tue Jul 24, 2007 8:25 am, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases.

Input:

Code: Select all

``````1111111111
100001
1000001
100000003
-100000007
2147483647
-2147483647
0``````
Output:

Code: Select all

``````1111111111 = 11 x 41 x 271 x 9091
100001 = 11 x 9091
1000001 = 101 x 9901
100000003 = 643 x 155521
-100000007 = -1 x 100000007
2147483647 = 2147483647
-2147483647 = -1 x 2147483647``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Code: Select all

``````
ACCEPTED

``````
abdullah how it can be?? may u explaine in brief???

Last edited by newton on Tue Jul 24, 2007 8:17 am, edited 1 time in total.

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Contact:
Newton,

As I remember their is no need to generat prime number. You can find the prime factors of a number(positive/negetive) without generating prime.

Try youself.

ABDULLAH.
We were in past, we are in past and we will go in past.

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

### Re: 583 RTE,help needed

Fuad Hassan EWU wrote: i am getting RTE. plz explain why. for what limit i will have to generate prime?
here is my code

Code: Select all

``````#include<stdio.h>
#include<iostream>
#include<math.h>
....
``````
First, Why you declare a long long(8 byte) type array for seiving..!! It is just a flag array.. so char or bool (1 byte) data type is good enough for that flaging of prime.

Second, Maximum number you need to prime factorize is : 2^31 -1 or 2147483647. So maximum prime you need to prime factorize that number is less then or equal to sqrt(214748367) so max = 50000 would be enough.

Third, As i already said, for prime factorizing a number maximum prime u need is less then or equal sqrt of that number.
So, Look at your code:

while(n>1){
while(n%prmcol==0){ // Here i is always increasing
........
}
i++;
}
Now if a number it self is a prime for example: 2147483647. your loop will try to access a memory index of 2147483647 of prmcol array!! Which is causing the RTE.
So use a break condition for stoping this blind loop.

NB:I have updated your code and PM you.. check the code there! But try to fix it by your self first.

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University
Thanks A1, It worked for me. and it really made my concepts clear.
thanks a lot.
Eagle er moto daana meley urbo

chinmoy kanti dhar
New poster
Posts: 19
Joined: Fri Jun 22, 2007 6:17 pm

### getting RTE

Why runtime error? help me plz

Code: Select all

``````#include<stdio.h>
#include<math.h>
#define ma 100000

long n;
void main()
{
long a[ma]={0},c,i,j,k,m,p[10000];
//prime
for(i=2;i<=sqrt(ma);i++)
if(a[i]==0)
for(j=i+i;j<=ma;j=j+i)a[j]=1;

j=1;
for(i=2;i<=ma;i++)
if(a[i]==0)p[j++]=i;

while(scanf("%ld",&n)==1)
{
if(n==0)break;

printf("%ld = ",n);m=0;
if(n<0){n=(-1)*n;printf("-1");m=1;}
c=n;

for(i=1;p[i]<=sqrt(c);i++)
{
while(1)
{
if(n%p[i]==0){n=n/p[i];if(m==1)printf(" x ");
printf("%ld",p[i]);m=1;}
else break;
}
if(n==1)break;

}if(n!=1){if(m==0)printf(" %ld",n);else printf(" x %ld",n);}
printf("\n");
}

}

``````

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
you should not put the prime number to the array. Solving the RTE u may get TLE.
ur program crash in that section:

for(i=1;p<=sqrt(c);i++)
{
while(1)
{
if(n%p==0){n=n/p;if(m==1)printf(" x ");
printf("%ld",p);m=1;}
else break;
}

while(1), causes OLE.

Starting from 2,3,5,7... divide the given number, and print it.
hope it will work.

aeiou
New poster
Posts: 21
Joined: Wed May 07, 2008 11:32 am

### 583 - Prime Factors TLE

Hello ,
ACed... Thanks to Jan..
Last edited by aeiou on Fri Jun 27, 2008 8:53 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 583 - Prime Factors

Well, if it gets TLE then you can store the primes first. And for each query try to divide it with the primes (not all the numbers).
Ami ekhono shopno dekhi...
HomePage

aeiou
New poster
Posts: 21
Joined: Wed May 07, 2008 11:32 am

### Re: 583 - Prime Factors

Thanks for the idea Jan...My code appears to be faster to me , I thought tat ll pass TL , but now precalculated the primes and got AC ...
Thank u very much...