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

Post Reply
User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Jun 06, 2007 8:50 am

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.
Instead of

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

Post by Deny Sutani » Wed Jun 06, 2007 6:50 pm

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

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

Post by Deny Sutani » Fri Jun 08, 2007 10:26 am

I try to change my code. It produces RE(Signal 8)

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?

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

583 RTE,help needed

Post by Fuad Hassan EWU » Wed Jul 18, 2007 10:55 pm

:o i am getting RTE. plz explain why. for what limit i will have to generate prime? :roll:
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

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

Post by newton » Sun Jul 22, 2007 12:43 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jul 22, 2007 2:12 pm

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

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

Post by newton » Mon Jul 23, 2007 2:44 pm

Code: Select all


    ACCEPTED

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

thanx in advanced
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
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Tue Jul 24, 2007 7:57 am

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

I think this will help you.
ABDULLAH.
We were in past, we are in past and we will go in past.

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Re: 583 RTE,help needed

Post by A1 » Sat Aug 04, 2007 7:44 pm

Fuad Hassan EWU wrote::o i am getting RTE. plz explain why. for what limit i will have to generate prime? :roll:
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. :)

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

Post by Fuad Hassan EWU » Sun Aug 05, 2007 12:47 am

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
Location: bangladesh

getting RTE

Post by chinmoy kanti dhar » Sat Aug 18, 2007 7:09 pm

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
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Wed Dec 19, 2007 11:06 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.

Instead of it:
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

Post by aeiou » Thu Jun 26, 2008 9:17 am

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
Location: Dhaka, Bangladesh
Contact:

Re: 583 - Prime Factors

Post by Jan » Fri Jun 27, 2008 8:03 am

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

Post by aeiou » Fri Jun 27, 2008 8:52 am

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

Post Reply

Return to “Volume 5 (500-599)”