# 工学1号馆

home

## Project Euler 29–Distinct powers

Wu Yudong    August 20, 2018     欧拉计划   556

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

1、将ab 进行因数分解，以字符串的形式保存，eg.  28= (4 * 7)= (22 * 7)5  = 2^10*7^5

2、用一个结构体数组保存所有的数的因数分解表达式

3、对上述结构体数组排序

4、遍历此数组，找出不相同的项的总数

// Language: C
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com
#include <stdio.h>
#include <string.h>

const int prim[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};

struct node
{
char list[100];

}num[9801];

int cmp(const void *a, const void *b)
{
return strcmp((*(struct node*)a).list, (*(struct node*)b).list);
}

char * explain(int a, int b)   /*将a^b分解因数*/
{
char s[100], ch;
char *p;
p = s;
int t;
for(int i = 0; i < 25; i++) {
t = 0;
while(a % prim[i] == 0) {
if(t == 0) {
sprintf(p,"%d",prim[i]);
}
a /= prim[i];
t++;
}
if(t > 0) {
p = s + strlen(s);
*p++ = '^';
t = t * b;
sprintf(p,"%d",t);
p = s + strlen(s);
if(a != 1) {
*p++ = '*';
} else {
break;
}
}
}
return s;
}

void solve(void)
{
int i, j, k, sum;
k = 0;
for(i = 2; i < 101; i++) {
for(j = 2; j < 101; j++) {
strcpy(num[k++].list, explain(i,j));
}
}
qsort(num, 9801, sizeof(num[0]),cmp);
sum = 1;
for(i = 0; i < 9801; ) {
j = i + 1;
if(j >= 9801)  break;
while(strcmp(num[i].list, num[j].list) == 0) {
j++;
}
i = j;
sum ++;
}
printf("%d\n",sum);
}

int main(void)
{
solve();
return 0;
}

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

#define N 101
#define M 601

int main(void)
{
int i, j, k, l;
bool flag[M];

bool use[N] = { false };

for (i = 2; i < N; i++) {
if (!use[i]) {
int t = i;

memset(flag, false, sizeof(flag));

for (j = 2; j < N; j++) {
t = t * i;
if (t >= N) {
break;
}
use[t] = true;
}

for (k = 1; k < j; k++) {
for (l = 2; l < N; l++) {
flag[k * l] = true;
}
}

for (k = 2; k < M; k++) {
if (flag[k]) {
}

}
}
}
return 0;
}