160 - Factors and Factorials

jambon_vn · Post by **jambon_vn** » Thu Sep 30, 2004 2:56 am

Thank guys. I have the same mistake. I got AC now.

afonsocsc · Post by **afonsocsc** » Wed Oct 27, 2004 1:52 am

Hi,
Check out inputs from 47 to 52.

chuzpa · Post by **chuzpa** » Fri Dec 31, 2004 1:02 pm

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 · Post by **Minerva** » Fri Dec 31, 2004 6:19 pm

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 · Post by **chuzpa** » Sat Jan 01, 2005 2:26 am

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 · Post by **Minerva** » Sat Jan 01, 2005 9:09 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 · Post by **chuzpa** » Sat Jan 01, 2005 11:18 am

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 · Post by **Andrey** » Sun Mar 06, 2005 10:41 pm

I don't know what's wrong in my code?

chunyi81 · Post by **chunyi81** » Mon Mar 07, 2005 4:08 pm

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.

Otherwise your output is fine.

sunnycare · Post by **sunnycare** » Tue Mar 15, 2005 2:58 am

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 · Post by **nicu_ivan** » Thu Mar 17, 2005 5:29 pm

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 · Post by **sunnycare** » Fri Mar 18, 2005 3:59 am

why use fstream?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Fri Mar 18, 2005 4:36 pm

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 · Post by **sunnycare** » Mon Mar 21, 2005 5:11 am

right..thanks..

ugrash · Post by **ugrash** » Fri Apr 01, 2005 2:10 pm

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

OJ Board

160 - Factors and Factorials

160 WA but why ??

160 WA

Why "Floating point exception"---problem 160

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

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