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

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 583 - Prime Factors

Post by x140l31 » Sun Jul 20, 2008 1:09 am

can anyone tell me why this produces a "core dumped"???

Code: Select all

int firstDiv(int &n, const VI &v)
{
    if (n < 0)
    {
        cout << "-1";
        n = -n;
        return 0;
    }
......
}
in concrete it crashes with n = -2147483647

-2147483647 and 2147483647 can be hold in an "int", no?

sorry about my poor english

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

Re: 583 - Prime Factors

Post by Jan » Mon Jul 21, 2008 9:41 pm

(+-)2147483647 both fit into normal int.
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 583 - Prime Factors

Post by x140l31 » Tue Jul 22, 2008 11:02 pm

Jan wrote:(+-)2147483647 both fit into normal int.
then why it crashes? :-?

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

Re: 583 - Prime Factors

Post by Jan » Tue Jul 22, 2008 11:29 pm

Can you post your full code?
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 583 - Prime Factors

Post by x140l31 » Wed Jul 23, 2008 12:20 am

Jan wrote:Can you post your full code?
this is not the code of 583 problem... but the function is similar:

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

int firstDiv(int &n, const VI &v)
{
    if (n < 0)
    {
        cout << "-1";
        n = -n;
        return 0;
    }
// here will be another portion of code
    return 0;
}

int main()
{
    int n;
    cin >> n;
    VI v(n);
    cout << firstDiv (n, v) << endl;
}
you can try this program, if you try this input, it will crash :-?

Code: Select all

-2147483647

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

Re: 583 - Prime Factors

Post by Jan » Fri Jul 25, 2008 12:43 am

Did you notice this?

Code: Select all

VI v(n);
You are giving -2147483647 as n. vector<int> v(-2147483647). That's why your program crashed.
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 583 - Prime Factors

Post by x140l31 » Sat Jul 26, 2008 1:53 am

Jan wrote:Did you notice this?

Code: Select all

VI v(n);
You are giving -2147483647 as n. vector<int> v(-2147483647). That's why your program crashed.
sorry sorry sorry!

i was wrong...

i give you the true code by mp

change those terrible mistake xD

Code: Select all

    #include <iostream>
    #include <vector>
    using namespace std;

    typedef vector<int> VI;
    typedef vector<VI> VVI;

    int firstDiv(int &n, const VI &v)
    {
        if (n < 0)
        {
            cout << "-1";
            n = -n;
            return 0;
        }
    // here will be another portion of code
        return 0;
    }

    int main()
    {
        int n;
        cin >> n;
        VI v(10000);
        cout << firstDiv (n, v) << endl;
    }

ihack
New poster
Posts: 1
Joined: Fri Aug 01, 2008 7:57 am

Re: 583 - Prime Factors

Post by ihack » Fri Aug 01, 2008 8:00 am

Jan wrote:(+-)2147483647 both fit into normal int.
if so ...why my code isnt working for 2147483647??

Code: Select all

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


int main()
{
	int n,i,minflag=0;
	while(scanf("%d",&n))
	{
		if(n==0)break;
		printf("%d = ",n);
		if (n<0)
		{
			minflag=1;
			printf("-1 x ");
			n=abs(n);
		}
		for(i=2;i*i<=n;i++)
		{
			while(n%i==0)
			{
				printf("%d",i);
				n/=i;
				if(n>1)printf(" x ");
			}
		}
		if(n!=1)
			printf("%d",n);
		
		printf("\n");


	}

	return 0;
}

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

Re: 583 - Prime Factors

Post by Jan » Thu Aug 21, 2008 5:06 pm

Code: Select all

for(i=2;i*i<=n;i++)
When n = 2147483647, suppose i*i is greater than n, but since i is an 'int' so, overflow will occur. Use i as 'long long'. Hope it helps.
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:

Re: 583 - Prime Factors TLE

Post by newton » Wed Sep 17, 2008 10:03 pm

why TLE plz help
whene i solved the problem after generating primes. But now if i dont handle only with primes the code gets TLE.

Code: Select all

#include <cstdio>

int absValue(int a){
	if(a<0)
		return -a;
	else
		return a;
}

int main(){
	int num,i;
	bool s;

	while(scanf("%d",&num) == 1 && num){
		s = false;

		if(absValue(num) == 1){
			printf("%d = %d\n",num,num);
			continue;
		}
		printf("%d =",num);
		if(num < 0){
			num = -num;
			s = true;
		}				
		if(s)
			printf(" -1 x");
		i = 2;
		while(num/i){
			if(num%i == 0){
				while(num%i == 0){
					num /= i;
					if(num/i == 0)
						printf(" %d",i);
					else
						printf(" %d x",i);
				}				
			}
			i++;
		}
		if(num>1){
			printf("x %d",num);
		}
		puts("");
	}
	return 0;
}
But as i am setting a condition
if(num%i == 0)
so this will process only the primes. So why still TLE?
Thanks

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 583 - Prime Factors TLE

Post by DJWS » Sun Sep 21, 2008 3:35 am

Because your algorithm is not efficient enough.
http://mathworld.wolfram.com/DirectSear ... ation.html
newton wrote:why TLE plz help
whene i solved the problem after generating primes. But now if i dont handle only with primes the code gets TLE.

Code: Select all

#include <cstdio>

int absValue(int a){
	if(a<0)
		return -a;
	else
		return a;
}

int main(){
	int num,i;
	bool s;

	while(scanf("%d",&num) == 1 && num){
		s = false;

		if(absValue(num) == 1){
			printf("%d = %d\n",num,num);
			continue;
		}
		printf("%d =",num);
		if(num < 0){
			num = -num;
			s = true;
		}				
		if(s)
			printf(" -1 x");
		i = 2;
		while(num/i){
			if(num%i == 0){
				while(num%i == 0){
					num /= i;
					if(num/i == 0)
						printf(" %d",i);
					else
						printf(" %d x",i);
				}				
			}
			i++;
		}
		if(num>1){
			printf("x %d",num);
		}
		puts("");
	}
	return 0;
}
But as i am setting a condition
if(num%i == 0)
so this will process only the primes. So why still TLE?
Thanks

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 583 - wht TLE ??

Post by abid_iut » Wed Nov 12, 2008 7:06 pm

i think my code is quite fast but why i am getting TLE??
please help me anyone :cry:

my code:

Code: Select all

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

typedef unsigned long inte;

void ptr(inte w){
	inte n=w;
	inte rez=0;

	inte i=2;int flag=0;
	while(i<=sqrt(w)+5){
		if(i>=sqrt(w) && flag!=0){cout<<n;break;}
		if(n%i==0){
			flag++;
				cout<<i;
				n/=i;
				if(n!=1)cout<<" x ";
				else break;
			
		}
		else {
			if(i==2)i++;
			else i+=2;
		}
		
	}
	if(flag==0)cout<<w;
}


int main()
{
	while(1){
		long n;cin>>n;
		if(n==0)break;
		cout<<n<<" = ";
		if(n<0){cout<<" -1 x ";n*=-1;}
		ptr(n);
		cout<<endl;
	}
	return 0;
}
Thanx in advance
plssss help.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 583 - Prime Factors

Post by pok » Wed Jan 07, 2009 11:27 pm

i'm getting Presentation error..
but i cant understand what is wrong ..
so pls help me..
Last edited by pok on Thu Jan 08, 2009 10:21 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 583 - Prime Factors

Post by mf » Thu Jan 08, 2009 12:39 am

Avoid printing trailing spaces at the end of each line.

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 583 - Prime Factors

Post by pok » Thu Jan 08, 2009 10:19 pm

Thanks a lot mf..
now AC..
take care..
God bless you.. :)

Post Reply

Return to “Volume 5 (500-599)”