[编程题]约数的个数
方法1：因子分解法
这一方法利用素数因子的特性
也就是求出质因数之后前面的组合乘上现在的因子加1
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 1010;
int main()
{
int k;
int total = 1;
int data;
int n;
//包含了1的参数
while(cin>>k)
{
for(int i=0;i<k;i++)
{
scanf("%d",&data);
total = 1;
//前面的因子为1
int currents;
for(int j=2;j<=sqrt(data);j++)
{
currents = 0;
while(data%j == 0)
{
data = data/j;
currents++;
}
//currents求出当前因子的指数
total = total*(currents+1);
//现在的约数个数为前面的组合个数乘上当前
//因子的指数加一
}
if(data == 1)
{
printf("%d\n",total);
//如果最后一个数为1时无法再分解
}
else
{
printf("%d\n",total*2);
//如果最后一个数字是素数的情况下
//相当于该素数的指数可以取0或1，所以乘2
}
}
}
return 0;
}
方法2：做除法求约数的个数
这种方法上面的大佬已经写过代码了，这里本菜鸡冒昧的借用一下
首先说明一下这种算法的方法，要想优化程序，必须要对于一个数循环到sqrt(该数字)，
否则线性查找必然超时
但是这样就产生一个问题，就是可能有些因数没有考虑进去
情况1：
比如说16的因子有2和8，但是你的循环只进行到sqrt(16)=4,这样的话约数8就会有遗漏
但是你知道在sqrt(16)的右边必然有一个约数8，因为两个数相乘要小于16，一个数小于sqrt(16),
一个数就要大于sqrt(16),所以这种情况下约数个数加2
情况2：这时候你就会发现约数4需要单独考虑一下，防止约数算重。
附上上面大佬的代码
#include<iostream>
usingnamespacestd;
int numOfDivisor(intnum)
{
int ans = 0;
int i;
for(i = 1; i*i<num; i++)
{
if(num%i == 0)
ans += 2;
//情况1
}
if(i*i == num) ans++;
//情况2
return ans;
}
int main()
{
int n, num;
while(cin >> n)
{
for(int i = 0; i<n; i++)
{
cin >> num;
cout << numOfDivisor(num) << endl;
}
}
return0;
}
编辑于 2020-03-01 12:53:37
回复(2)
import java.util.Scanner;public class Main { public static void main(String args[]){ Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int shuge = sc.nextInt(); int[] wo = new int[shuge]; for(int i=0;i<shuge;i++){ int count = 0; int shu = sc.nextInt();for(int j=1;j<=Math.sqrt(shu);j++){ if(shu%j==0){ count++; } } wo[i] = count; } for(int i=0;i<wo.length;i++){ System.out.println(wo[i]*2); } } sc.close(); } }
发表于 2017-11-18 14:57:51
回复(0)
#include <stdio.h>
#include <string.h>
#define LENGTH 100010
int prime[LENGTH];
int mark[LENGTH];
int primeSize = 0;
int cnt[LENGTH];
void initPrime() {
memset(mark, 0, sizeof(mark));
for (int i = 2; i < LENGTH; i++) {
if (mark[i] == 0) {
for (int j = i * i; j >= 0 && j < LENGTH; j += i) {
mark[j] = 1;
}
}
}
for (int i = 2; i < LENGTH; i++) {
if (mark[i] == 0) {
prime[primeSize++] = i;
// printf("%d\n", i);
}
}
}
int solution(int num) {
int n = num;
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < primeSize; i++) {
while (num % prime[i] == 0) {
cnt[i]++;
num /= prime[i];
}
}
int ans = 1;
for (int i = 0; i < primeSize; i++) {
if (prime[i] > n)
break;
ans *= (cnt[i] + 1);
}
if (num != 1)
ans *= 2;
return ans;
}
int main() {
int N;
int num;
initPrime();
while (scanf("%d", &N) != EOF && N != 0) {
for (int i = 0; i < N; i++) {
scanf("%d", &num);
printf("%d\n", solution(num));
}
}
return 0;
}
我还以为要分解质因数，原来暴力算也能过啊
发表于 2017-10-30 21:21:39
回复(1)
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int M = 4e4;
vector<int> v;
bool isPrime[M];
void init(){
fill(isPrime, isPrime + M, true);
isPrime[0] = false;
isPrime[1] = false;
for(int i = 2;i < M;i++){
if(!isPrime[i]) continue;
v.push_back(i);
if(i > M / i) continue;
for(int j = i * i;j < M;j += i) isPrime[j] = false;
}
}
int main(){
int n, m;
init();
int num = v.size();
while(scanf("%d", &n) != EOF){
if(n == 0) break;
for(int i = 0;i < n;i++){
scanf("%d", &m);
if(m == 1) cout<<1<<endl;
else{
int bound = sqrt(m);
int total = 1;
for(int i = 0;i < num;i++){
if(m < v[i]) break;
int count = 0;
while(m % v[i] == 0){
count++;
m /= v[i];
}
total *= (count + 1);
}
if(m > 1) total *= 2; //本身算一个约数，所以count=1
cout<<total<<endl;
}
}
}
return 0;
}
发表于 2022-01-25 18:26:32
回复(0)
#include<iostream>
#include<cmath>
using namespace std;
int numOfDivisor(int num)
{
int ans = 0;
int i = 0;
if(num==1)
return 1;
for(i=1;i*i<num;i++)
{
if(num%i==0)
{
ans+=2;//一个因子小于i，一个因子大于i
}
}
if(i*i==num) ans++;
return ans;
}
int main()
{
int n;
cin>>n;
for(int i = 0;i<n;i++)
{
int t;
cin>>t;
cout<<numOfDivisor(t)<<endl;
}
}
#include<cmath>
using namespace std;
int numOfDivisor(int num)
{
int ans = 0;
int i = 0;
if(num==1)
return 1;
for(i=1;i*i<num;i++)
{
if(num%i==0)
{
ans+=2;//一个因子小于i，一个因子大于i
}
}
if(i*i==num) ans++;
return ans;
}
int main()
{
int n;
cin>>n;
for(int i = 0;i<n;i++)
{
int t;
cin>>t;
cout<<numOfDivisor(t)<<endl;
}
}
发表于 2021-04-01 21:56:21
回复(0)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 4e4;
bool arr[MAX];
vector<int> prime;
vector<int> pre;
void initial()
{
for (int i = 2; i < MAX; i++)
{
arr[i] = true;
}
for (int i = 2; i < MAX; i++)
{
if (!arr[i])
{
continue;
}
prime.push_back(i);
for (int j = 2 * i; j < MAX; j += i)
{
arr[j] = false;
}
}
}
int getNum(int tmp)
{
int res = 1;
for (int i = 0; i < prime.size(); i++)
{
if (tmp < prime[i])
{
break;
}
int total = 0;
while (tmp % prime[i] == 0)
{
total++;
tmp /= prime[i];
}
pre.push_back(total);
}
if (tmp > 1)
{
pre.push_back(1);
}
for (int i = 0; i < pre.size(); i++)
{
res *= (pre[i] + 1);
}
return res;
}
int main()
{
initial();
int n, tmp;
while (cin >> n)
{
for (int i = 0; i < n; i++)
{
cin >> tmp;
cout << getNum(tmp) << endl;
pre.clear();
}
}
return EXIT_SUCCESS;
}
发表于 2021-02-19 15:03:57
回复(0)
#include <stdio.h>
#define max 100000
int write[10000];
void findnumber()
{
int number[max];
number[0]=1;
number[1]=1;
int j=2;
int tag=0;
for(j=2;j<max;j++)
{
int i=j;
if(number[i]==0)
{
write[tag++]=i;
int k=2;
while(i*k<max)
{
number[i*k]=1;
k++;
}
}
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
findnumber();
int j=0;
// for(j=0;j<10000;j++)
// printf("%d ",write[j]);
int i=0;
for(j=0;j<n;j++)
{
int number;
scanf("%d",&number);
int answer=1;
for(i=0;i<1000;i++)
{
int result=0;
while(number%write[i]==0)
{
number/=write[i];
result++;
}
answer=(result+1)*answer;
}
//这是要很值得注意的一点
if(number>1)
answer=answer*2;
printf("%d\n",answer);
}
}
return 0;
} 请教一下，这个代码输出结果是正确的，但是为什么错误呢
发表于 2021-01-22 20:59:35
回复(0)
/*
*素数筛得到素数表
*遍历素数表拿质因子并记录个数
*质因子个数加一累积即结果
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5; //数据1e9 质因子最大sqrt(n) (约1e4.5)即可，如果没能除尽，则仅剩一个质因子大于sqrt(n)
int primes[maxn+5];
bool isPrime[maxn+5];
int facts[maxn+5];
int cnt;
/* 欧拉筛 竟然没埃氏筛快 可能是数据1e5太小吧
void getPrimes() //欧拉筛
{
fill(isPrime, isPrime+maxn, true);
isPrime[0] = isPrime[1] = false;
for(int i = 2;i <= maxn; i++)
{
if(isPrime[i]) primes[cnt++] = i;
for(int j = 1;j < cnt && primes[j]*i <= maxn; j++)
{
isPrime[primes[j]*i] = false;
if(i % primes[j] == 0) break;
}
}
}
*/
void getPrimes() //埃氏筛
{
cnt = 0;
fill(isPrime, isPrime+maxn, true);
isPrime[0] = isPrime[1] = false;
for(int i = 2;i <= maxn; i++)
{
if(isPrime[i])
{
primes[cnt++] = i;
for(int j = i+i;j <= maxn;j += i)
isPrime[j] = false;
}
}
}
int getFacts(int n) //得到一个数的各个质因子个数 然后各个个数加一累乘就是这个是的因子的个数
{
if(n == 1) return 1;
int h = sqrt(n), ans = 1, cnt2 = 0;
for(int i = 0;primes[i] <= h; i++)
{
if(n % primes[i] == 0)
{
facts[cnt2] = 0;
while(n % primes[i] == 0)
{
facts[cnt2]++; n /= primes[i];
}
cnt2++;
if(n == 1) break;
}
}
if(n > 1) facts[cnt2++] = 1;
for(int i = 0;i < cnt2; i++) ans *= (facts[i]+1);
return ans;
}
int main()
{
int n, x;
getPrimes();
while(scanf("%d",&n) == 1)
{
for(int i = 0;i < n; i++)
{
scanf("%d",&x); printf("%d\n", getFacts(x));
}
}
return 0;
}
发表于 2021-01-19 14:49:01
回复(0)
比如求20的约数：1,2,4,5,10,20
事实上我们不需要讲所有数字都试一遍，如果20可以被1整除，则其商20一定也为其约数；如果20可以被2整除，那其商10一定也为其约数。在这种情况下，可以一次增加两个约数。
再比如求16的约数：1,2,4,8,16
由于16=4*4，但是我们只能算4一个约数，所以一旦该数字是一个数的平方时，我们只需要统计枚举到小于该数的根号（这时候每次增加2个约数，(1,16)，(2,8)），然后加上4这1个值就行。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] strArr = br.readLine().split(" ");
for(int i = 0; i < strArr.length; i++)
System.out.println(solve(Integer.parseInt(strArr[i]))); // 直接计算每个数的约数个数并进行输出
}
private static int solve(int n){
int count = 0;
int i;
for(i = 1; i*i < n; i++)
if(n % i == 0) count += 2;
if(i*i == n)
count ++;
return count;
}
}
编辑于 2021-01-07 16:36:40
回复(0)
//考虑时间限制所以%j 的边界值不是a[i]了 j*j<a[i] i+=2比j小的一个约数比j大的一个约数
#include<stdio.h>
int main()
{
int n,i,j;
int a[1000],num;
scanf("%d",&n);//输入
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)//输入的每个数
{
num=0;
for(j=1;j*j<a[i];j++)
if(a[i]%j==0)//可以整除
num+=2;
if(j*j==a[i])//两个约数相等所以+1
num++;
printf("%d\n",num);
}
return 0;
}
编辑于 2020-03-21 15:05:48
回复(0)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
void approximation(int*,int*,int);
int n,*p1,*p2,i;
scanf("%d",&n);
p1=(int*)malloc(sizeof(int)*n);
p2=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++){
scanf("%d",p1+i);}
approximation(p1,p2,n);
for(i=0;i<n;i++){
printf("%d\n",*(p2+i));}
free(p1);
free(p2);
return 0;
}
void approximation(int* p1,int* p2,int n){
int i,j,temp;
for(i=0;i<n;i++)
*(p2+i)=0;
for(i=0;i<n;i++){
temp=(int)sqrt((double)*(p1+i));
for(j=1;j<=temp;j++){
if(*(p1+i)%j==0)
(*(p2+i))+=2;
}
if(temp*temp==*(p1+i))
(*(p2+i))--;
}
}
#include<stdlib.h>
#include<math.h>
int main(){
void approximation(int*,int*,int);
int n,*p1,*p2,i;
scanf("%d",&n);
p1=(int*)malloc(sizeof(int)*n);
p2=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++){
scanf("%d",p1+i);}
approximation(p1,p2,n);
for(i=0;i<n;i++){
printf("%d\n",*(p2+i));}
free(p1);
free(p2);
return 0;
}
void approximation(int* p1,int* p2,int n){
int i,j,temp;
for(i=0;i<n;i++)
*(p2+i)=0;
for(i=0;i<n;i++){
temp=(int)sqrt((double)*(p1+i));
for(j=1;j<=temp;j++){
if(*(p1+i)%j==0)
(*(p2+i))+=2;
}
if(temp*temp==*(p1+i))
(*(p2+i))--;
}
}
发表于 2020-03-08 17:03:07
回复(0)
必须要使用 sqrt()等函数来减小循环的量 否则只有超时GG~
#include <iostream>
#include <math.h>using namespace std;
int main(){
int n,sum,i,j;
while(cin>>n){
int a[n];
for(i=0;i<n;i++){
cin>>a[i];
sum=0;
for(j=1;j<sqrt(a[i]);j++){
if(a[i]%j==0) sum+=2;
}
if(pow(j,2)==a[i]) sum++;
cout<<sum<<endl;
}
}
return 0;
}
发表于 2019-11-15 22:34:29
回复(0)
//求素数的思想，缩小遍历范围
//约数都是成对出现，
#include<stdio.h>
#include<math.h>
void divisor(long num[],int divi[],int n){ int i,j;//1和本身一定是约数 for(i=0;i<n;i++){ int count=2; int bound=(int)sqrt(num[i]);//需要强制类型转换 //if(bound*bound==num[i])//正好开平方，如9=3*3 // count++; for(j=2;j<=bound;j++){ if(0==num[i]%j) count+=2;//约数都是成对出现， } if(bound*bound==num[i])//正好开平方，如9=3*3 count--; divi[i]=count; }
}
int main(){ long num[1000]; int divi[1000]; int n,i; while(scanf("%d",&n)!=EOF){ if (0==n) break; else{ for(i=0;i<n;i++){ scanf("%ld",&num[i]); } divisor(num,divi,n);//求约数个数 for(i=0;i<n;i++) printf("%d\n",divi[i]);//输出每个数的约数个数，换行输出 } } return 0;
}
发表于 2018-03-26 22:00:07
回复(0)
#include<stdio.h>
#include<math.h>
int main()
{
int N,a[1000],b[1000],i,j,t;
while(scanf("%d",&N)!=EOF)
{
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
b[i]=0;
}
for(i=0;i<N;i++)
{
t=sqrt(a[i]);
for(j=1;j<=t;j++)
if(a[i]%j==0) b[i]++;
if(t*t==a[i])
b[i]=2*b[i]-1;
else b[i]*=2;
}
for(i=0;i<N;i++)
printf("%d\n",b[i]);
}
return 0;
}
#include<math.h>
int main()
{
int N,a[1000],b[1000],i,j,t;
while(scanf("%d",&N)!=EOF)
{
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
b[i]=0;
}
for(i=0;i<N;i++)
{
t=sqrt(a[i]);
for(j=1;j<=t;j++)
if(a[i]%j==0) b[i]++;
if(t*t==a[i])
b[i]=2*b[i]-1;
else b[i]*=2;
}
for(i=0;i<N;i++)
printf("%d\n",b[i]);
}
return 0;
}
发表于 2018-01-12 10:47:18
回复(1)
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
int N=0;
int temp=0;
int divisor=0;
int t=0;
vector<int> element;
cin>>N;
if(N>1000&&N<=0)return 0;
while(N){
cin>>temp;
if(temp>100000000&&temp<1){
cout<<"超过范围";
return 0;}
element.push_back(temp);
N--;
}
for(int i=0;i<element.size();i++){
temp=element[i];
t=(int)sqrt(temp);
for(int j=1;j<=t;j++){
if(temp%j==0&&j==t) divisor++;
else if(temp%j==0)divisor+=2;
}
cout<<divisor<<endl;
divisor=0;
}
return 0;
}
问题的关键优化是开方sqrt(),因为偶的复试竟然是手写笔试程序，所以范围都得加判断。
编辑于 2017-02-24 15:53:33
回复(0)
题目关键是sqrt()函数，不仅避免一对约数重复计算，而且还能找出是否存在一对相同的约数
#include<stdio.h>
#include<math.h>
long long int sum_prime (int n);
int main()
{
int n, i;
long long int temp;
while (scanf("%d", &n) != EOF){
for (i = 0; i < n; i++){
scanf("%lld", &temp);
printf("%lld\n", sum_prime (temp));
}
}
return 0;
}
\
long long int sum_prime (int n)
{
long long int sum = 0, i;
for (i = 1; i <= sqrt(n); i++){
if (n % i == 0){
if (i == sqrt(n)){
sum += 1;
}else{
sum += 2;
}
}
}
return sum;
}
发表于 2016-12-10 19:44:30
回复(2)
import java.util.Scanner;
public class Main{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
while(in.hasNext())
{
int n=in.nextInt();
int dataArray[]=new int[n];
for(int i=0;i<n;i++)
{
dataArray[i]=in.nextInt();
}
int times=0;
for(int i=0;i<dataArray.length;i++)
{ if(dataArray[i]<0){
System.out.println(1);
}
else{
for(int j=1;j<=Math.sqrt(dataArray[i]);j++){
if(dataArray[i]%j==0)
times++;
}
System.out.println(times*2);
times=0;
}
}
}
in.close();
}
}
发表于 2016-04-10 11:10:12
回复(7)
#include <cstdio>
#include <cmath>
int main()
{
int n;
while( scanf("%d",&n)!=EOF && n != 0 )
{
long num,sum = 0;
for( int i=0; i<n; i++)
{
scanf("%ld",&num);
int j;
if( num>0 )
{
for( j=1; j*j<num; j++ )
if( num%j==0 ) sum += 2;
if( j*j==num ) sum++;
}
else sum = 1;
printf("%ld\n",sum);
sum = 0;
}
}
return 0;
}
发表于 2016-04-08 14:12:43
回复(0)
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int num;
cin >> num;
if (num == 0) {
return 0;
}
int * number = new int[num];
for (int i = 0; i < num; i++) {
cin >> number[i];
}
int count = 0;
int i,j;
for (i = 0; i < num; i++) {
for ( j = 1; j <= sqrt(number[i]); j++) {
if (number[i]%j == 0){
count ++;
}
}
cout << count*2 << endl;
count = 0;
}
return 0;
}
主要就是判断一个数 i 有几个约数时从1循环到sqrt(i)即可，不然运行时间会超出要求
发表于 2016-05-29 12:12:44
回复(2)
利用平方根，可以减少遍历范围，如果s = a * b，若s % a == 0，那么a,b均为s的约数，并且a和b中只有一个<sqrt(s)。如果从1开始遍历，时间复杂度过大，会超时。如果s=a*a，这时只能计算为一个约数~
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
int a[n];
int yueshu[n] = {0};
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++){
int num;
for(num = 1; num * num < a[i]; num++){
if(a[i] % num == 0){
yueshu[i] += 2;
}
}
if(num * num == a[i]) yueshu[i]++;
}
for(int i = 0; i < n; i++) cout << yueshu[i] << endl;
}
return 0;
}
编辑于 2018-05-26 14:15:56
回复(0)
问题信息
难度：
224条回答
333收藏
30316浏览
通过挑战的用户
查看代码-
2023-03-13 11:27:41
-
2023-03-07 15:22:34 -
2023-03-06 13:37:46 -
2023-03-02 23:43:43
-
2023-02-28 20:20:37
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
