このプログラムをより速くするにはどうすればよいですか？

Question

割り当ては、整数kを読み込み、正確にk個の除数を持つ正の整数 を1〜100000（両端を含む）の数だけ出力します。たとえば、番号24には、 1,2,3,4,6,8,12,24の8つの約数があります。

私は実行中のプログラムを持っていますが、検索が高速になる可能性がありますか？ ？

#include <stdio.h> 
#include <math.h> 


int main(void) 
{ int a; //user input// 
    int divisors; //running total of number of divisors// 
    int sum; //running total of numbers with the required number of divisors// 

    printf("Enter the target number of divisors:"); 
    scanf("%d", &a); 
    printf("\n"); 

    int i; 
    for (i=1; i<=100000; i++) 
    { 
      divisors=2; 
      int p; 
      for(p=2; p<i; p++) 
      {if (i%p==0) 
      divisors++;} 

     if (divisors==a) 
     sum++;} 

    printf("There are %d numbers between 1 and 100000 inclusive which have exactly %d divisors.", sum, a); 

return 0; 
} 

Answer 1

例コード。 iとpの宣言を古いC型コンパイラ（Microsoft/Visual Studioを使用しています）との互換性のために移動しました。 ceil（sqrt（i））の外側ループを使用します。コードは入力1を処理します（数字1には1除数しかありません）。 2の入力は、100,000未満の素数の数を出力します（100,000未満の9592個の素数があります）。

この方法では、2100万回を超える反復が必要です。反復回数〜= .67 n sqrt（n）。

#include <stdio.h> 

int main(void) 
{ 
    int a;   /* user input */ 
    int divisors; /* total number of divisors */ 
    int sum;  /* count of numbers with required number of divisors */ 
    int i;   /* moved here for C compiler */ 
    int p;   /* moved here for C compiler */ 
    int sqrti;  /* ceil(sqrt(i)) */ 

    printf("Enter the target number of divisors: "); 
    scanf("%d", &a); 
    printf("\n"); 
    sum = 0;       /* init sum */ 
    sqrti = 1;       /* init sqrti */ 
    for (i = 1; i <= 100000; i++) 
    { 
     divisors = 0;     /* init number of divisors */ 
     if(sqrti*sqrti < i)    /* update sqrti as needed */ 
      sqrti += 1; 
     for(p = 1; p < sqrti; p++) 
      if(i%p == 0)    /* if p is a divisor, count it and i/p */ 
       divisors += 2; 
     if(p*p == i)     /* if p*p == i, count it */ 
      divisors += 1; 
     if (divisors == a)    /* if i has a divisors, increment sum */ 
      sum += 1; 
    } 
    printf("There are %d numbers from 1 to 100000 inclusive which have exactly %d divisors.\n", sum, a); 
    return 0; 
} 

配列が素数の篩法と同様に使用できる場合、このメソッドは100万回以上の反復を必要とします。反復回数〜= n ln（n）。

#include <stdio.h> 
#define n 100000 
int main(void) 
{ 
int * cnt = (int *)calloc(n+1, sizeof(int)); 
int d; 
    printf("Enter the target number of divisors: "); 
    scanf("%d", &d); 
    /* time complexity O(n log(n)) */ 
    { 
    int i, j; 
     for (i = 1; i <= n; i++) { 
      for(j = i; j <= n; j += i) { 
       cnt[j]++; 
      } 
     } 
    } 
    { 
    int i; 
    int sum = 0; 
     for (i = 1; i <= n; i++) 
      sum += (cnt[i] == d) ? 1 : 0; 
     printf("excactly %d numbers have %d divisors\n", sum, d); 
    } 
    free(cnt); 
    return 0; 
} 

Answer 2

むしろi uptil pの値をチェックするよりも、我々はsqrt(i)までチェックし、代わりの1 divisorsを増分することによって最適化することができ、我々は数のための1つkためi及び第二で割っ言う2によってそれをincreament番号i/k。

n=1000000; 

for (i=1; i<=10000; i++) 
    { 
      divisors=2; 
      int p; 
      for(p=2; p<=sqrt(i); p++) 
      { 
       if (i%p==0) 
       { 
        if(p != (i/p) 
         divisors = divisors + 2; 
        else 
         divisors++; 
       } 
      } 

     if (divisors==a) 
     sum++; 
}