Page **1** of **2**

### 516 - Prime Land

Posted: **Thu Jan 23, 2003 4:06 pm**

by **deddy one**

help, pls check my code

[cpp]#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#define max 35000

int count [max];

main () {

long int i,j,m,last;

char line[10000];

char *p;

long root;

int input [max];

while (gets (line)) {

if (strcmp (line,"0") == 0) break;

memset (input,0,sizeof (input));

memset (count,0,sizeof (count));

i = 0;

p = strtok (line," ");

input[i++] = atoi(p);

while (p!= NULL)

{

p = strtok (NULL," ");

input[i++] = atoi (p);

}

i--;

m = 1;

for (j=0;j<i;j+=2)

{

m *= (pow(input[j],input[j+1]));

}

m--;

last= 0;

root = (long int)sqrt (m);

for (i=2;;i++)

{

if (i>last) last = i;

if (i > root ) {count[m]++;last = m;break;}

while (!(m%i)) {

count * ++;*

m /= i;

}

if (m==1) break;

}

for (i=last;i>=0;i--)

{

if (count* !=0)*

printf ("%ld %d ",i,count*);*

}

printf ("\n");

}

return 0;

}[/cpp]

Posted: **Sun Feb 16, 2003 8:18 pm**

by **deddy one**

forget it, the problem is only at my strtok.

fixed it and get PE

Posted: **Fri Feb 21, 2003 8:39 am**

by **anupam**

yes, be careful while using strtok with while..

and always check for break properly.

### 516re(SIGFPE)

Posted: **Fri Aug 01, 2003 8:39 am**

by **lendlice**

I found where is wrong with my code.

Posted: **Fri Aug 01, 2003 9:06 am**

by **titid_gede**

RTE SIGSFE is occured when there is division by zero. check your division / mod.

### 516 keep on WA

Posted: **Sun Aug 31, 2003 1:52 pm**

by **boatfish**

I really don't know why this code keeps on WA.

It passes all test cases that I can think about.

[cpp]#include<iostream>

#include<string>

#include<math.h>

using namespace std;

struct src{

int p;

int e;

};

src table[32768];

void factor(int result){

int limit=sqrt(result),no=0,i,t=0;

for(i=2;i<=limit;i++,no=0){

if(result%i==0){

(table[t]).p=i;

while(result%i==0){

result/=i;

no++;

}

(table[t]).e=no;

t++;

}

}

t--;

if(result!=1){

cout<<result<<" 1";

return;

}

for(i=t;i>=0;i--)

cout<<(table*).p<<' '<<(table**).e<<' ';*

}

int main(){

string t;

int i,result,length,e,p,end;

while(getline(cin,t)){

if(t=="0")

break;

result=1;

length=t.length();

for(i=0;i<length;){

end=t.find(' ',i);

p=atoi((t.substr(i,end-i)).c_str());

i=end+1;

end=t.find(' ',i);

if(end!=string::npos){

e=atoi((t.substr(i,end-i)).c_str());

i=end+1;

}

else{

e=atoi((t.substr(i)).c_str());

result*=pow(p,e);

break;

}

result*=pow(p,e);

}

result--;

factor(result);

cout<<endl;

}

return 0;

}

[/cpp]

### 516 why TLE?

Posted: **Fri Nov 28, 2003 1:04 pm**

by **harshahs**

I am getting correct solution for all the input between 3 and INT_MAX, that too instantly, with this code for 516. why OJ is giving TLE?

please help.

[c]

#include <stdio.h>

#include <math.h>

#include <string.h>

unsigned stack[100];

int main(void)

{

char str[80];

unsigned register base,exp,i,val,temp;

while(1)

{

gets(str);

val = 1;

if(strcmp(str,"0")==0)

return 0;

i = 0;

while(str* >= '0' && str** <= '9')*

{

base = 0;

while(str* != ' ')*

{

base = base*10 + (str* - '0');*

i++;

}

i++;

exp = 0;

while(str* != ' ' && str**)*

{

exp = exp*10 + (str* - '0');*

i++;

}

i++;

val *= (unsigned)pow(base,exp);

}

val--;

temp = (unsigned)sqrt(val);

temp++;

exp = 0,i=0;

while(!(val%2))

{

exp++;

val /= 2;

}

if(exp)

{

stack[i++] = 2;

stack[i++] = exp;

}

base = 3;

while(val != 1 || base <= temp)

{

exp = 0;

while(!(val%base))

{

exp++;

val /= base;

}

if(exp)

{

stack[i++] = base;

stack[i++] = exp;

}

base += 2;

}

if(val != 1)

{

stack[i++] = val;

stack[i++] = 1;

}

printf("%d %d",stack[--i],stack[--i]);

while(i)

{

printf(" %d %d",stack[--i],stack[--i]);

}

printf("\n");

}

return 0;

}

[/c]

### 516WA

Posted: **Tue Jun 22, 2004 5:33 pm**

by **Eduard**

Can somebody give me some test cases.I can't understand why I'm getting WA.

[pascal]label 1;

var a:array[0..41000] of byte;

s,i,j,k,n,p:longint;

function parz(n:longint):boolean;

var i:longint;

begin

parz:=true;

for i:=2 to trunc(sqrt(n)) do

if n mod i= 0 then

begin

parz:=false;

break;

end;

end;

procedure solve(n:longint);

var i,j,g:longint;

begin

i:=trunc(sqrt(n));

i:=i+1;

repeat

i:=i-1;

if a*=1 then*

if n mod i=0 then

begin

g:=0;

repeat

if n mod i=0 then begin g:=g+1;n:=n div i;end;

until n mod i<>0;

write(i,' ',g,' ');

end;

until (n=1);

end;

begin

a[0]:=0;

a[1]:=0;

for i:=2 to 40000 do

if parz(i) then a*:=1 else a**:=0;*

repeat

s:=1;

while not eoln do

begin

read(p);

if p=0 then goto 1;

read(j);

k:=1;

for i:=1 to j do

k:=k*p;

s:=s*k;

end;

readln;

s:=s-1;

solve(s);

writeln;

until 1=2;

1:

end.

[/pascal]

### some input & output of 516

Posted: **Sun Oct 31, 2004 7:13 am**

by **Rocky**

input:

18 1 17 1 15 1

17 1 11 1

11 1 29 1 9 1

2 1 4 1 5 1 7 1 11 1

18 1 23 1 29 1

31 1 29 1

2 3 11 2 25 1

41 2

51 1 5 1

17 1 19 1 23 1

0

output:

code:

353 1 13 1

31 1 3 1 2 1

41 1 7 1 5 1 2 1

3079 1

7 4 5 1

449 1 2 1

3457 1 7 1

7 1 5 1 3 1 2 4

127 1 2 1

619 1 3 1 2 2

i could not understand your pascel code.by the way this is the output of my accepted code for following input.try now.it might help you BY

### 516 Prime Land

Posted: **Tue May 10, 2005 1:40 pm**

by **kenneth**

Hi, I have developed the solution for this question and have tested it with all numbers from 2 to 32767. Checked the prime factorization is correct. I have printed them out in descending order as well. (I have written a few codes to test these properties). However, the online judge still said my answer is incorrect. I really can't see why my answer is incorrect.

Would anyonen be able to identify the reason for me??

Thanks

Code removed after AC.

Posted: **Fri May 13, 2005 3:00 am**

by **sahand**

You're not initializing the 'count' variable in genFac() function.

You should always initialize variables unless they are global, or static.

And, the way you start your program:

Code: Select all

```
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <stdio.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); i++)
```

is not good at all. I think most C++ programmer's agree with me on these points:

- Don't include headers if you don't need them.

- Don't use macros in that way.

Hope it helped

Posted: **Sat Sep 03, 2005 3:20 pm**

by **kenneth**

Thanks a lot for your help.

I did not realize I have not initialize the value >.< (but it's strangely that I still got the right answer on my own compiler....)

The reason I put all header files in is to such that I don't have to type them up one by one when I try different questions =)

Posted: **Sun Nov 19, 2006 11:41 pm**

by **marius_siuram**

I tried with this test cases, with my own ones, and the examples and it seems to me that it runs well, but the judge says an WA.

Code: Select all

```
#include <iostream>
#include <sstream>
#include <string>
#define MAXPRIME 181
#define MAXTERMS 30
using namespace std;
// these primes are the necessary ones (there are few)
// from 2 to the sqrt of the maximum
int LISTPRIMES[] = { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 ,
43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 ,
109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 999};
// last one indicates end of everything
// reducing the number is more efficient (easier to work with smaller numbers)
// that's why *orig is changed and passed by reference
int numfactors (int * orig , int factor)
{
int n;
n = 0;
while ( *orig % factor == 0 )
{
*orig = *orig / factor;
n++;
}
return n;
}
void addfactor (int * orig, int factor, int exp)
{
for ( ; exp > 0 ; exp-- )
{
*orig = *orig * factor;
}
}
int main ()
{
string oneline;
int number;
int base, exp, i;
int solution[MAXTERMS],isol;
while ( 1 )
{
//get each line (one number per line)
getline (cin , oneline);
stringstream feeder ( oneline );
//make the number
number = 1;
while ( !feeder.eof () )
{
feeder >> base;
// zero -> exit
if ( base == 0 ) return (0);
feeder >> exp;
addfactor (&number, base, exp);
}
// now do the minus 1 and proceed to factorize
number--;
isol = 0;
i = 0;
while ( ( LISTPRIMES[i] < MAXPRIME+1 ) && ( (LISTPRIMES[i]*LISTPRIMES[i]) < number ) )
{
if ( number % LISTPRIMES[i] == 0 )
{
solution[isol] = LISTPRIMES[i];
solution[isol + 1] = numfactors ( &number , LISTPRIMES[i] );
isol+=2;
}
i++;
}
// if number is still big then it must be a prime
if ( number > 1 )
{
solution[isol] = number;
solution[isol + 1] = 1;
isol +=2;
}
// now we have to print inverting the order
isol -= 2;
cout << solution[isol] << " " << solution[isol + 1];
isol -= 2;
for ( ; isol > -1 ; isol -= 2 )
{
cout << " " << solution[isol] << " " << solution [isol + 1];
}
cout << endl;
}
return (0);
}
```

Well ... some silly thing maybe? I suppose that primes until 181 are quite enough (the text of 516 says that the number to do the minus one will be less or equal than 32767, and 181 is its sqrt). I was too lazy to implement a cribe of erathostenes (or however it is spelled).

Posted: **Wed Nov 22, 2006 5:50 pm**

by **Jan**

I have made a file consisting of Rocky's input. And ran your code. Your code didnot pass the samples. But when I gave input by hand your code produced right. Just make a input file and run your code. You have to fix it.

Posted: **Wed Nov 29, 2006 10:27 pm**

by **marius_siuram**

mmmm wow, thanks. I see then, something weird is happening, and I didn't expect that type of problem (something with the endlines-code or similar). I'll fix that soon I hope.

Thanks a lot!