约数的个数

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

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

我还以为要分解质因数，原来暴力算也能过啊

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

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

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

/*
*素数筛得到素数表
*遍历素数表拿质因子并记录个数
*质因子个数加一累积即结果
*/


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

//考虑时间限制所以%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;
}

//求素数的思想，缩小遍历范围
//约数都是成对出现，

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

	

#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(),因为偶的复试竟然是手写笔试程序，所以范围都得加判断。

题目关键是sqrt()函数，不仅避免一对约数重复计算，而且还能找出是否存在一对相同的约数

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

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

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

//i*i<num的形式，数值稳定性更好
#include<iostream>
using namespace std;
int numOfDivisor(int num)
{
	int ans = 0;
	int i;
	for (i = 1; i*i<num; i++)
	{
		if (num%i == 0)
			ans += 2;
	}
	if (i*i == num) ans++;
	return ans;
}
int main()
{
	int n, num;
	while (cin >> n)
	{
		for (int i = 0; i<n; i++)
		{
			cin >> num;
			cout << numOfDivisor(num) << endl;
		}
	}
	return 0;
}