Page 7 of 12

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

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.

Posted: Wed Jun 06, 2007 6:50 pm
by Deny Sutani
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.

Posted: Fri Jun 08, 2007 10:26 am
by Deny Sutani
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?

583 RTE,help needed

Posted: Wed Jul 18, 2007 10:55 pm
by Fuad Hassan EWU
: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 


Posted: Sun Jul 22, 2007 12:43 pm
by newton
thanx to all.

Code: Select all

  Accepted

Posted: Sun Jul 22, 2007 2:12 pm
by Jan
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.

Posted: Mon Jul 23, 2007 2:44 pm
by newton

Code: Select all


    ACCEPTED

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

thanx in advanced

Posted: Tue Jul 24, 2007 7:57 am
by abdullah<cse du>
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.

Re: 583 RTE,help needed

Posted: Sat Aug 04, 2007 7:44 pm
by A1
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. :)

Posted: Sun Aug 05, 2007 12:47 am
by Fuad Hassan EWU
Thanks A1, It worked for me. and it really made my concepts clear.
thanks a lot. :)

getting RTE

Posted: Sat Aug 18, 2007 7:09 pm
by chinmoy kanti dhar
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");
}


}


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

583 - Prime Factors TLE

Posted: Thu Jun 26, 2008 9:17 am
by aeiou
Hello ,
ACed... Thanks to Jan..

Re: 583 - Prime Factors

Posted: Fri Jun 27, 2008 8:03 am
by Jan
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).

Re: 583 - Prime Factors

Posted: Fri Jun 27, 2008 8:52 am
by aeiou
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...