只算因数个数的话,能简化到分解质因数
[ 本帖最后由 azzbcc 于 2013-3-20 15:20 编辑 ]
[ 本帖最后由 azzbcc 于 2013-3-20 15:20 编辑 ]
[fly]存在即是合理[/fly]
#include <time.h> #include <math.h> #include <stdio.h> #include <string.h> int a[240] = {0}; void InitArray(int n) { int i, temp = 2, j; for (i = a[0];i > 0;a[i--] = 0); for (i = 2, j = 1;n != 1;++i) { if (n % i) continue; if (temp != i) { j += !!a[j]; temp = i; } n /= i--, ++a[j]; } a[0] = j; } int main() { clock_t t2, t1 = clock(); int j, temp; for (int i = 1000000;i > 240;--i) { InitArray(i); for (temp = j = 1;j <= a[0];++j) temp *= a[j] + 1; if (temp == 240) printf("%d\t", i); } puts(""); t2 = clock(); printf("%.3f s\n", (t2-t1)/1000.0); return 0; }
#include <time.h> #include <math.h> #include <stdio.h> int a[240] = {0}; int ss[1230] = {2, 3, 5, 7, 11, 13, 17, 19}; void Init() { //10000以内质数表,1229个 int i, j, k = 8, temp; for (i = 23;k != 1230;i += 2) { temp = (int)sqrt(i); for (j = 0;ss[j] <= temp;++j) { if (i % ss[j]) continue; break; } if (ss[j] <= temp) continue; ss[k++] = i; } } void InitArray(int n) { //把 n分解质因数,指数部分依次存入数组 a,a[0]存储有效数位 // 例如 240 = 2 ^ 4 * 3 * 5,则 数组 a:3 4 1 1 int i, temp = 2, j; int s = (int)sqrt(n); for (i = a[0];i > 0;a[i--] = 0); //数组 a清 0 for (i = 0, j = 1;n != 1 && ss[i] <= s;++i) { if (n % ss[i]) continue; if (temp != ss[i]) { j += !!a[j]; temp = ss[i]; } n /= ss[i--], ++a[j]; } if (1 != n) ++a[j += !!a[j]]; a[0] = j; } int main() { clock_t t2, t1 = clock(); int j, temp;Init(); for (int i = 100000000;i >= 240;--i) { InitArray(i); //按数组 a求出因数个数,240的因数个数为 (4+1)*(1+1)*(1+1) = 20 for (temp = j = 1;j <= a[0];++j) temp *= a[j] + 1; if (temp >= 240) printf("%10d\t", i); } puts(""); t2 = clock(); printf("%.3f s\n", (t2-t1)/1000.0); return 0; }