10699 - Count the factors

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

Moderator: Board moderators

Malohkan
New poster
Posts: 2
Joined: Sat Oct 09, 2004 1:18 am

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

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?
Last edited by Malohkan on Mon Oct 11, 2004 8:00 pm, edited 1 time in total.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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
New poster
Posts: 2
Joined: Sat Oct 09, 2004 1:18 am

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
New poster
Posts: 2
Joined: Sat Oct 30, 2004 12:27 am

10699 - Count the factors

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

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

Turing
New poster
Posts: 2
Joined: Sat Oct 30, 2004 12:27 am

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..:D
Anyway, now can you shine some light???
Turing

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

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

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

nice!

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
New poster
Posts: 8
Joined: Sat May 21, 2005 2:13 am

10699 WA Whyyyyyyyyyyyy??

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
New poster
Posts: 3
Joined: Tue Oct 26, 2004 6:05 pm
Location: Latin America

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
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

10699

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);
	}
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: RTE_10699

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
New poster
Posts: 1
Joined: Tue Dec 13, 2005 10:01 am

Re: RTE_10699

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: RTE_10699

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 :wink:

Post Reply

Return to “Volume 106 (10600-10699)”