10699

Malohkan · Post by **Malohkan** » Sat Oct 09, 2004 1:20 am

I submitted a solution to problem 10699 and got this error:

gcj: Internal compiler error: program jc1 got fatal signal 11

Here is my code:

Code: Select all

import java.io.IOException;

//10699
class Main {
    
    static String ReadLn (int maxLg) {  // utility function to read from stdin
	    byte lin[] = new byte [maxLg];
	    int lg = 0, car = -1;
        
        try {
            while (lg < maxLg) {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e) {
            return null;
        }

        if ((car < 0) && (lg == 0))
            return null;  // eof
        
        return new String (lin, 0, lg);
    }

    public static void main(String[] args) {
        
        String line;
        while ( !(line = ReadLn(255)).equals("0")) {
            
            int toEvaluate = Integer.parseInt(line);
            System.out.print(toEvaluate + " : ");
            
            int count = 0;
            int limit = (int)Math.ceil(Math.sqrt(toEvaluate));
            int lastCounted = 0;
            
            for (int i = 2; i < limit; i++) {
                if (toEvaluate % i == 0) {
                    if (i != lastCounted)
                        count++;
                    lastCounted = i;
                    
                    toEvaluate /= i;
                    i--;
                }
            }
            
            if (toEvaluate != 1)
                count++;
            
            System.out.println(count);
        }
    }
}

What is wrong with that? The most complicated thing I use is String. The ReadLn code is taken straight from the Java example. What am I doing wrong?

Maniac · Post by **Maniac** » Mon Oct 11, 2004 3:41 pm

I also get these kind of compiler errors sometimes. I always get them when I use something like

Code: Select all

node[from].neighbour[node[from].neighbours++] = node[to];

When I then get this error, I change my code to

Code: Select all

Node n1 = node[from];
Node n2 = node[to];
n1.neighbour[n1.neighbours++] = n2;

and that helps! God knows why....

Anyway, looking at your code you could try changing

Code: Select all

while ( !(line = ReadLn(255)).equals("0")) {

into

Code: Select all

while (true) {
line = ReadLn(255);
if(line.equals("0")) break;

Maybe that helps in your case. Good luck!

Erik

P.S. better remove your ID from your post

Malohkan · Post by **Malohkan** » Mon Oct 11, 2004 9:27 pm

I now use:

Code: Select all

String line = ReadLn(255);
while (!line.equals("0")) {
	//blah blah
	//blah blah

	System.out.println(answer);
	line = ReadLn(255);
}

And it got accepted, woo! Thank you very much!

Turing · Post by **Turing** » Sat Oct 30, 2004 12:30 am

I don't understand the term "different prime factors".
Whats the ans for 6?
Shouldn't it be 2? If not, why??? 6=2*3 I presume, and 2 and 4 are the "distinct" prime factors.
Somebody shine some light on this one!!
Turing

sohel · Post by **sohel** » Sat Oct 30, 2004 6:04 am

Turing wrote: Whats the ans for 6?
Shouldn't it be 2? If not, why??? 6=2*3 I presume, and 2 and 4 are the "distinct" prime factors.

You are right.. 6 has 2 distinct prime factors, namely(2 and 3)...
.. but how did you get 4 to be a prime factor of 6..( 4 is not a prime number at all)..

consider 100:
100 = 2 * 2 * 5 * 5

So number of distinct prime factor for 100 is also 2( namely 2 and 5).

Hope it helps.

Turing · Post by **Turing** » Sat Oct 30, 2004 8:40 pm

Wow..
You see..sometimes the hand gets a little jerky and ..
you get the point
I meant "2 and 3 are distinct prime factors of 6".
not 4..

Anyway, now can you shine some light???
Turing

muvee · Post by **muvee** » Tue Dec 14, 2004 8:38 pm

I've gotten "Accepted" with time of 0.6 s and 8864 of memory..
I thought this would be pretty good. When I open the ranklist, the first page is full of 0.00 guys !! How did you guys do it.

My Algo :

- Find all the primes upto 1000000
- For each number upto 1000000, find it's largest prime divisor
- For each input, find the prime factorization using the array I have constructed in step 2
- Sort the list of prime factors
- Count number of unique factors

I'm getting 0.6 seconds for this and I honestly can't think of an algo that would take 0.00 seconds and have negligible memory requirements!

Adrian Kuegel · Post by **Adrian Kuegel** » Tue Dec 14, 2004 8:45 pm

For factoring a number n with simple method of dividing by primes, you only need to try to divide by primes up to sqrt(n), because if you tried all these prime factors, then the remaining factor of n must be a prime. Why? Simply because if it would be no prime, it would consist of at least two prime factors p*q, and you already tried all prime factors up to sqrt(n), so p*q > sqrt(n)*sqrt(n) = n.
So for this problem it means you only need primes up to 1000.

muvee · Post by **muvee** » Tue Dec 14, 2004 9:39 pm

Thanks Adrian

I incorporated that slick piece of info into my code and now I'm getting 0.006 with 64 mem usage. Then I changed my cout into printf and it further improved to 0.002 !! I guess I can improve that further if I improve my method of finding primes upto 1000 but 0.002 is good enough

Thanks again.

vivander · Post by **vivander** » Fri May 27, 2005 4:15 am

I have probed a lot of cases for this problem, and aparent, the code is OK but I have W.A. and I don't know why it is.

Can anybody help my?

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>


int main(){
	
	int contador, flag;
	long int i, j=0,primos[100000],numero,aux,num;
	char linea[105];
	
	for(i=0;i<100000;i++) primos[i]=1;
	
    for(i=2;i<=500000;i++) { 
		flag=0; 
		num=2; 
		while((num<=sqrt(i))&&(flag==0)) { 
			if((i%num)==0) flag=1; 
			else num++; 
		  } 
		if(flag==0) { 
			j++;			
			primos[j]=i; 
		} 
	}		

	while(fgets(linea,105,stdin)!=NULL){
		sscanf(linea,"%ld",&numero);
		if (numero==0) return 1;
		
		aux=numero;
		contador=0;
		
		for(i=j;i>0;i--){
			if (numero==1) break;
			else if (numero%primos[i]==0) { 
				numero /= primos[i];
				while (numero%primos[i]==0) numero /= primos[i];
				contador++;
			 }
		  }
		printf("%ld : %d\n",aux,contador);
		
	}
	
	return 1;
}

milo · Post by **milo** » Sat May 28, 2005 2:05 am

I don't know where exactly is your error, but for the case where n=700001 my AC program gives 1, and your program gives 0.

Espero te sirva.

mohsincsedu · Post by **mohsincsedu** » Sun Oct 23, 2005 1:58 am

Why RTE?? Plz help me!!!

Code: Select all

#include<stdio.h>
#include<math.h>

#define MAX 1002

long prime[MAX];

void main()
{
	long i,j,n,count;
	for(i = 3;i<MAX;i+=2)
		prime[i] = 1;
	for(i = 3;i*i<MAX;i+=2)
	{
		if(prime[i])
		{
			for(j = i*i;j<MAX;j+=i)
				prime[j] = 0;
		}
	}
	prime[0] = 2;
	for(i = 3,j = 1;i<MAX-1;i+=2)
		if(prime[i])
			prime[j++] = i;
	while(scanf("%ld",&n)==1)
	{
		if(!n)
			break;
		printf("%ld : ",n);
		count = i = 0;
		while(n>1)
		{
			if(n%prime[i]==0)
			{
				while(n%prime[i]==0)
				{
					n/=prime[i];
				}
				count++;
			}
			i++;
		}
		printf("%ld\n",count);
	}
}

Martin Macko · Post by **Martin Macko** » Sat Dec 10, 2005 11:39 pm

mohsincsedu wrote:Why RTE?? Plz help me!!!

It gives Floating point exception for 930887.

FTLuna · Post by **FTLuna** » Tue Dec 13, 2005 10:12 am

mohsincsedu wrote:Why RTE?? Plz help me!!!

I got RTE, too, and I dont know why.

I use the same way to solve the problem as you.

Martin Macko · Post by **Martin Macko** » Tue Dec 13, 2005 1:08 pm

FTLuna wrote:
mohsincsedu wrote:Why RTE?? Plz help me!!!
I got RTE, too, and I dont know why.

Well, you probably have some bug in your code... Try some really big and/or tricky test cases. If nothing helps you can still post your code here

OJ Board

10699 - Count the factors

gcj: Internal compiler error: program jc1 got fatal signal 1

10699 - Count the factors

10699 .. Count the factors... How in the world ??!?!

nice!

10699 WA Whyyyyyyyyyyyy??

Re: RTE_10699

Re: RTE_10699

Re: RTE_10699