算法实验题1-4反素数.pptVIP

算法实验题1-4反素数 学号：130321006 姓名：戴晓翔 ★实验任务 对于正整数x，将其约数个数记为n(x)。例如n(1)=1，n(6)=4。如果某个正整数x满足：对于任意i(0ix)都有n(i)n(x)，则称x为反素数。 现在给定一个区间[a,b]，请你求出该区间的x使n(x)最大。 ★数据输入 输入数据为两个正整数a和b，1=a=b=5000，表示闭区间[a,b]。 ★数据输出 输出为一个整数，为该区间因子最多的数。如果满足条件有多个，则输出其中最小的数。 输入示例 输出示例 2 3 2 输入示例 输出示例 1 10 6 计算某个数的约数的个数 算法描述 int main() { int a, b, c, x, i, n, nMax; cin a b; c=a; i=0; nMax=0; if (a=1 ab b=5000) { for(x=a;x=b;x++) { n=0; for(i=1;i=x;i++) { if (x%i==0) n++; } if (nnMax) { nMax=n; c=x; } } cout c endl; } if (a==b) cout c endl; return 0; } 变量说明： a、b为数据输入的区间范围 c为最终输入的结果，即该区间中约数个数最多的数中最小的数 n为每个数的约数个数 nMax为最多的约数的个数 利用循环语句，对每个数求约数的个数 找约数个数最多的 算法复杂度分析 O（n2）