## 160 - Factors and Factorials

Moderator: Board moderators

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am
Thank guys. I have the same mistake. I got AC now.

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon
Hi,
Check out inputs from 47 to 52.

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

### 160 WA but why ??

Could someone help me ?. I've tried to correct the output format, and the results of the outputs seams to be right :S.

here's the code ...

#include <stdio.h>
#define X 101

int p[X],N,k=0,a[X],used[X],u[X],t;

isPrime (int x){
int i,r;
for(i=2;i<x;i++)
if (x%i==0)
return 0;

return 1;
}

void generatePrimes(){
int i;

p[k++]=2;
for(i=3;k<=N;i++)
if (isPrime( i ))
p[k++] = i;
}

void copy(){
int i;
for(i=0;i<N;i++)
used+=u;

}

void wichPrimesMake(long long x, long long mult,int ind){
int calc = mult*p[ind],i;

if (calc>x || t)
return;

mult = calc;
u[ind]++;

if (mult == x){
copy();
t = 1;
u[ind]--;
return;
}
for(i=0;i<=x;i++)
if((mult*p)<=x)
wichPrimesMake(x,mult,i);
u[ind]--;
}

int busbin(int x){
int desde=0,hasta=k-1,m;

do{
if (p[desde]==x)return desde;
if (p[hasta]==x)return hasta;

m = (desde+hasta)/2;
if (p[m]==x)return m;

if (p[m]>x)
hasta = m-1;

if (p[m]<x)
desde = m+1;

}while(desde<hasta);
return -1;
}

void ff(int d){
int i,j,x;

for(i=d;i<=N;i++){

x = busbin(i);

if (x!=-1)
used[x]++;

else{
t = 0;
for(j=0;j<k;j++){
wichPrimesMake(i,1,j);
if(t)break;
}
}
}
}

void impr(){
int i,f=0;

printf("%3d! = ",N);
for(i=0;p<=N;i++){
if (i==15 && p[i+1]<=N)
printf("\n ");

printf("%3d",used);
}
printf("\n");

}

void limpia(){
int i;
for(i=0;i<=N;i++)
used=0;

}

int main(){
int lastn,desde;
N = 100;
generatePrimes();

while(scanf("%d",&N)!=EOF){
if (N<2)continue;

if(N<lastn){
limpia();
desde = 2;
}
else
desde = lastn+1;

if (N==lastn){impr(); continue;}

ff(desde);
impr();
lastn=N;
}

return 0;
}

thanx for the help!

Minerva
New poster
Posts: 2
Joined: Thu Nov 25, 2004 10:43 am
I run ur program on my PC, I found that ur program can't output the answer, and I also think the solution to the problem is very easy ---- just
creat a prime list ---- prime[num_prime] and define an integer array to record the num ---- sum[num_prime], then do as the following things:
int point = 0;
while ( N / prime[point] !=0 && point < num_prime){
int p = prime[point];
while ( N / p != 0){
sum[point] += (N / p);
p *= prime[point];
}
point++;
}

I am not good at English, but I hope you can understand what I say, also I hope you can get AC. Good luck !

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:
hi, yeap I know i'ts very simple but in my computer it does have an output :S, in fact are these ones, are them wrong ?

Code: Select all

``````  2! =   1
3! =   1  1
4! =   3  1
5! =   3  1  1
6! =   4  2  1
7! =   4  2  1  1
8! =   7  2  1  1
9! =   7  4  1  1
10! =   8  4  2  1
11! =   8  4  2  1  1
12! =  10  5  2  1  1
13! =  10  5  2  1  1  1
14! =  11  5  2  2  1  1
15! =  11  6  3  2  1  1
16! =  15  6  3  2  1  1
17! =  15  6  3  2  1  1  1
18! =  16  8  3  2  1  1  1
19! =  16  8  3  2  1  1  1  1
20! =  18  8  4  2  1  1  1  1
21! =  18  9  4  3  1  1  1  1
22! =  19  9  4  3  2  1  1  1
23! =  19  9  4  3  2  1  1  1  1
24! =  22 10  4  3  2  1  1  1  1
25! =  22 10  6  3  2  1  1  1  1
26! =  23 10  6  3  2  2  1  1  1
27! =  23 13  6  3  2  2  1  1  1
28! =  25 13  6  4  2  2  1  1  1
29! =  25 13  6  4  2  2  1  1  1  1
30! =  26 14  7  4  2  2  1  1  1  1
31! =  26 14  7  4  2  2  1  1  1  1  1
32! =  31 14  7  4  2  2  1  1  1  1  1
33! =  31 15  7  4  3  2  1  1  1  1  1
34! =  32 15  7  4  3  2  2  1  1  1  1
35! =  32 15  8  5  3  2  2  1  1  1  1
36! =  34 17  8  5  3  2  2  1  1  1  1
37! =  34 17  8  5  3  2  2  1  1  1  1  1
38! =  35 17  8  5  3  2  2  2  1  1  1  1
39! =  35 18  8  5  3  3  2  2  1  1  1  1
40! =  38 18  9  5  3  3  2  2  1  1  1  1
41! =  38 18  9  5  3  3  2  2  1  1  1  1  1
42! =  39 19  9  6  3  3  2  2  1  1  1  1  1
43! =  39 19  9  6  3  3  2  2  1  1  1  1  1  1
44! =  41 19  9  6  4  3  2  2  1  1  1  1  1  1
45! =  41 21 10  6  4  3  2  2  1  1  1  1  1  1
46! =  42 21 10  6  4  3  2  2  2  1  1  1  1  1
47! =  42 21 10  6  4  3  2  2  2  1  1  1  1  1  1
48! =  46 22 10  6  4  3  2  2  2  1  1  1  1  1  1
49! =  46 22 10  8  4  3  2  2  2  1  1  1  1  1  1
50! =  47 22 12  8  4  3  2  2  2  1  1  1  1  1  1
51! =  47 23 12  8  4  3  3  2  2  1  1  1  1  1  1
52! =  49 23 12  8  4  4  3  2  2  1  1  1  1  1  1
53! =  49 23 12  8  4  4  3  2  2  1  1  1  1  1  1  1
54! =  50 26 12  8  4  4  3  2  2  1  1  1  1  1  1  1
55! =  50 26 13  8  5  4  3  2  2  1  1  1  1  1  1  1
56! =  53 26 13  9  5  4  3  2  2  1  1  1  1  1  1  1
57! =  53 27 13  9  5  4  3  3  2  1  1  1  1  1  1  1
58! =  54 27 13  9  5  4  3  3  2  2  1  1  1  1  1  1
59! =  54 27 13  9  5  4  3  3  2  2  1  1  1  1  1
1  1
60! =  56 28 14  9  5  4  3  3  2  2  1  1  1  1  1
1  1
61! =  56 28 14  9  5  4  3  3  2  2  1  1  1  1  1
1  1  1
62! =  57 28 14  9  5  4  3  3  2  2  2  1  1  1  1
1  1  1
63! =  57 30 14 10  5  4  3  3  2  2  2  1  1  1  1
1  1  1
64! =  63 30 14 10  5  4  3  3  2  2  2  1  1  1  1
1  1  1
65! =  63 30 15 10  5  5  3  3  2  2  2  1  1  1  1
1  1  1
66! =  64 31 15 10  6  5  3  3  2  2  2  1  1  1  1
1  1  1
67! =  64 31 15 10  6  5  3  3  2  2  2  1  1  1  1
1  1  1  1
68! =  66 31 15 10  6  5  4  3  2  2  2  1  1  1  1
1  1  1  1
69! =  66 32 15 10  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1
70! =  67 32 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1
71! =  67 32 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1  1
72! =  70 34 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1  1
73! =  70 34 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1  1  1
74! =  71 34 16 11  6  5  4  3  3  2  2  2  1  1  1
1  1  1  1  1  1
75! =  71 35 18 11  6  5  4  3  3  2  2  2  1  1  1
1  1  1  1  1  1
76! =  73 35 18 11  6  5  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1
77! =  73 35 18 12  7  5  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1
78! =  74 36 18 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1
79! =  74 36 18 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1  1
80! =  78 36 19 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1  1
81! =  78 40 19 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1  1
82! =  79 40 19 12  7  6  4  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1
83! =  79 40 19 12  7  6  4  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1  1
84! =  81 41 19 13  7  6  4  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1  1
85! =  81 41 20 13  7  6  5  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1  1
86! =  82 41 20 13  7  6  5  4  3  2  2  2  2  2  1
1  1  1  1  1  1  1  1
87! =  82 42 20 13  7  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1
88! =  85 42 20 13  8  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1
89! =  85 42 20 13  8  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
90! =  86 44 21 13  8  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
91! =  86 44 21 14  8  7  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
92! =  88 44 21 14  8  7  5  4  4  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
93! =  88 45 21 14  8  7  5  4  4  3  3  2  2  2  1
1  1  1  1  1  1  1  1  1
94! =  89 45 21 14  8  7  5  4  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1
95! =  89 45 22 14  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1
96! =  94 46 22 14  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1
97! =  94 46 22 14  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1
98! =  95 46 22 16  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1
99! =  95 48 22 16  9  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1
100! =  97 48 24 16  9  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1
``````

Minerva
New poster
Posts: 2
Joined: Thu Nov 25, 2004 10:43 am
I have found the mistake !!!

If the input is :
5
6
7
8
9
12
5
10
22
3
4
12
0
My AC program's output is :
5! = 3 1 1
6! = 4 2 1
7! = 4 2 1 1
8! = 7 2 1 1
9! = 7 4 1 1
12! = 10 5 2 1 1
5! = 3 1 1
10! = 8 4 2 1
22! = 19 9 4 3 2 1 1 1
3! = 1 1
4! = 3 1
12! = 10 5 2 1 1
But ur's output is :
5! = 3 1 1
6! = 4 2 1
7! = 4 2 1 1
8! = 7 2 1 1
9! = 7 4 1 1
12! = 10 5 2 1 1
5! = 3 1 1
10! = 8 4 2 1
22! = 19 9 4 3 2 1 1 1
3! = 1 1
4! = 3 1
12! = 10 5 2 1 3
Why the same input data but different output?

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:
thanks a lot!, I've got AC! well . P.E, but that's o.k for me , I was not cleaning well an array .

thanks again!!

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

### 160 WA

I don't know what's wrong in my code?
Last edited by Andrey on Tue Mar 08, 2005 11:49 am, edited 1 time in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
I ran your code with some inputs
Your code give arithmetic exception with maxn >= 97

Also, your code doesn't handle more than one input properly.

Try with the following input:

53
54

Notice that output for 54 is joined to the second of output for 53.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

### Why "Floating point exception"---problem 160

Code: Select all

``````#include <iostream>

using namespace std;

unsigned long primeTable[25]={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};
unsigned long func(unsigned long n,unsigned long p)
{
unsigned long i=0;
while(n>0)
{
n=n/p;
i+=n;
}
return i;
}
void main()
{

unsigned long n;
cin>>n;
while(n!=0)
{

cout.width(3);
cout.setf(ios::right);
cout<<n;
cout<<"! =";

for(unsigned long i=0;primeTable[i]<=n;i++)
{
if(i==15)
cout<<endl<<"      ";

cout.width(3);
cout.setf(ios::right);
cout<<func(n,primeTable[i]);

}
cout<<endl;

cin>>n;

}

}``````
the judhe said:
Your program has died with signal 8 (SIGFPE). Meaning:

Floating point exception

Before crash, it ran during 0.000 seconds.

nicu_ivan
New poster
Posts: 7
Joined: Wed Mar 16, 2005 7:27 pm

### Re: Why "Floating point exception"---problem 160

Trie this source, try not to use iostream.h but fstream.h
sunnycare wrote:

Code: Select all

``````#include <fstream>

using namespace std;

unsigned long primeTable[25]={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};
unsigned long func(unsigned long n,unsigned long p)
{
unsigned long i=0;
while(n>0)
{
n=n/p;
i+=n;
}
return i;
}
void main()
{

unsigned long n;
cin>>n;
while(n!=0)
{

cout.width(3);
cout.setf(ios::right);
cout<<n;
cout<<"! =";

for(unsigned long i=0;primeTable[i]<=n;i++)
{
if(i==15)
cout<<endl<<"      ";

cout.width(3);
cout.setf(ios::right);
cout<<func(n,primeTable[i]);

}
cout<<endl;

cin>>n;

}

}``````
the judhe said:
Your program has died with signal 8 (SIGFPE). Meaning:

Floating point exception

Before crash, it ran during 0.000 seconds.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
why use fstream?

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Good question - why? I'd like to know too

The code crashes for a simple reason. Assume that the next value after primeTable is 0. What will happen?

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
right..thanks..

ugrash
New poster
Posts: 5
Joined: Fri Apr 01, 2005 2:06 pm

### 160 WA ?? (I've already searched in the forum :))

Hi,

I am always WA, I checked my output and can't find any error.
Heelp !

#include <stdio.h>

int premiers[25];
int entree[99];
int nbrentres;
int res[25];
int resultats[99][25];
int maxis[99];
int maxx;

void decompose(int *max, int nbr)
{
int k=0, j;
*max = 0;
for (j=0;j<25;j++) res[j]=0;
while (nbr != 1)
{
if (nbr % premiers[k] == 0)
{
nbr = nbr / premiers[k];
res[k] = res[k] + 1;
*max = k;
}
else k++;
}
}

void calcstok(int nbr)
{
int i, j, mx=0;
if (maxis[nbr - 2] == -1)
{
for(i=maxx+1;i<nbr-1;i++)
{
decompose(&mx, i+2);
for(j=0;j<25;j++) resultats[j] = resultats[i-1][j] + res[j];
maxis=mx>maxis[i-1]?mx:maxis[i-1];
maxx = nbr-2;
}
}
}

int main(int argc, char *argv[])
{
int i,j,k,m;
k = maxx = nbrentres = 0;
premiers[0] = 2;
premiers[1] = 3;
premiers[2] = 5;
premiers[3] = 7;
premiers[4] = 11;
premiers[5] = 13;
premiers[6] = 17;
premiers[7] = 19;
premiers[8] = 23;
premiers[9] = 29;
premiers[10] = 31;
premiers[11] = 37;
premiers[12] = 41;
premiers[13] = 43;
premiers[14] = 47;
premiers[15] = 53;
premiers[16] = 59;
premiers[17] = 61;
premiers[18] = 67;
premiers[19] = 71;
premiers[20] = 73;
premiers[21] = 79;
premiers[22] = 83;
premiers[23] = 89;
premiers[24] = 97;
for(j=0;j<99;j++)
{
for(i=0;i<25;i++) resultats[j] = 0;
maxis[j] = -1;
entree[j] = 0;
}
maxis[0] = 0;
resultats[0][0] = 1;
while (scanf("%d",&m)==1)
{
if (m!=0) entree[k++] = m; else break;
nbrentres++;
}
for (k=0;k<nbrentres;k++)
{
m = entree[k];
calcstok(m);
printf("%3d! =",m);
for(i=0;i<maxis[m-2]+1;i++)
{
printf("%3d",resultats[m-2]);
if ((i+1)%15 == 0) printf("\n ");
}
printf("\n");
}
return 0;
}