## 516 - Prime Land

Moderator: Board moderators

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

### 516 - Prime Land

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;
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]

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
forget it, the problem is only at my strtok.

fixed it and get PE

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
yes, be careful while using strtok with while..
and always check for break properly.
"Everything should be made simple, but not always simpler"

lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

### 516re(SIGFPE)

I found where is wrong with my code.
Last edited by lendlice on Tue Aug 05, 2003 7:33 am, edited 1 time in total.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
RTE SIGSFE is occured when there is division by zero. check your division / mod.
Kalo mau kaya, buat apa sekolah?

boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

### 516 keep on WA

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;

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]

harshahs
New poster
Posts: 8
Joined: Wed Oct 22, 2003 3:58 pm

### 516 why TLE?

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?

[c]
#include <stdio.h>
#include <math.h>
#include <string.h>

unsigned stack;

int main(void)
{
char str;
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]

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 516WA

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;
a:=0;
for i:=2 to 40000 do
if parz(i) then a:=1 else a:=0;
repeat
s:=1;
while not eoln do
begin
if p=0 then goto 1;
k:=1;
for i:=1 to j do
k:=k*p;
s:=s*k;
end;
s:=s-1;
solve(s);
writeln;
until 1=2;
1:
end.
[/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

### some input & output of 516

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

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

### 516 Prime Land

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.
Last edited by kenneth on Sat Sep 03, 2005 3:22 pm, edited 1 time in total.

sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Contact:
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 kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am
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 =)

marius_siuram
New poster
Posts: 2
Joined: Sat Nov 18, 2006 12:56 am
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;

}

// 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).

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm