計數不同的素數因子

Question

我必須計算2到100000之間的不同素數因子的數量，是否有比我所做的更快的方法？ 。 即2具有1個不同的素數因子2 10具有2個不同的素數因子（2,5） 12具有2個不同的素數因子（2,3） 我的代碼： -

#include<stdio.h> 
#include<math.h> 
typedef unsigned long long ull; 
char prime[100000]={0}; 
int P[10000],fact[100000],k; 

void sieve() 
{ 
    int i,j; 
    P[k++]=2; 
    for(i=3;i*i<1000;i+=2)  
    { 
      if(!prime[i]) 
      { 
        P[k++]=i; 
        for(j=i*i;j<100000;j+=i+i)  
          prime[j] = 1; 
      } 
    } 
    for(i=1001;i<100000;i+=2)  
      if(!prime[i]) 
        P[k++]=i; 
} 

int calc_fact() { 
    int root,i,count,j; 
    fact[1]=fact[2]=fact[3]=1; 
    for(i=4;i<=100000;i++) { 
    count=0; 
    root=i/2+1; 
    for(j=0;P[j]<=root;j++) { 
     if(i%P[j]==0)count++; 
    } 
    if(count==0) fact[i]=1; 
    else fact[i]=count; 
    } 
return 0; 
} 
int main(){ 
int i; 
sieve(); 
calc_fact(); 
for(i=1;i<10000;i++) printf("%d ,",fact[i]); 
return 0; 
} 

Answer 1

您可以輕鬆地適應Erasthotenes的篩來算素數因子的數了。

下面是用C實現，有一些測試一起：

#include <stdio.h> 

#define N 100000 

static int factorCount[N+1]; 

int main(void) 
{ 
    int i, j; 

    for (i = 0; i <= N; i++) { 
     factorCount[i] = 0; 
    } 

    for (i = 2; i <= N; i++) { 
     if (factorCount[i] == 0) { // Number is prime 
      for (j = i; j <= N; j += i) { 
       factorCount[j]++; 
      } 
     } 
    } 

    printf("2 has %i distinct prime factors\n", factorCount[2]); 
    printf("10 has %i distinct prime factors\n", factorCount[10]); 
    printf("11111 has %i distinct prime factors\n", factorCount[11111]); 
    printf("12345 has %i distinct prime factors\n", factorCount[12345]); 
    printf("30030 has %i distinct prime factors\n", factorCount[30030]); 
    printf("45678 has %i distinct prime factors\n", factorCount[45678]); 

    return 0; 
} 

Answer 2

有許多快速主要搜索算法。希望這個鏈接幫助：Which is the fastest algorithm to find prime numbers?

Answer 3

你可以做一個Eratosthenes篩子更好。

在Python

N = 100000 
M = int(N**.5)       # M is the floor of sqrt(N) 
nb_of_fact = [0]*N 
for i in xrange(2,M): 
    if nb_of_fact[i] == 0:    # test wether i is prime 
     for j in xrange(i,N,i):  # loop through the multiples of i 
      nb_of_fact[j] += 1 
for i in xrange(M,N): 
    if nb_of_fact[i] == 0: 
     nb_of_fact[i] = 1 

在循環結束時，nb_of_fact [i]是第i個素因子的數量（特別是1當且僅當i是素數）。

舊版本錯誤

N = 100000 
nb_of_fact = [1]*N 
for i in xrange(2,N): 
    if nb_of_fact[i] == 1:    # test wether i is prime 
     for j in xrange(2*i,N,i):  # loop through the multiples of i 
      nb_of_fact[j] += 1 

Answer 4

這個功能通常被稱爲小歐米加。您可能會發現一些有用的 鏈接here