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

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

(+-)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

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

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

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

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

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

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

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

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

### Re: 583 - Prime Factors TLE

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

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

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

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

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

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

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