подсчет различных основных факторов

Question

Мне нужно подсчитать количество различных основных факторов более 2 до 100000, есть ли какой-нибудь быстрый метод, чем то, что я делаю? . т.е. 2 имеет 1 отчетливый простой множитель 2 10 имеет два различных простого фактор (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

Вы можете определенно сделать лучше, сделав сито Эратосфена.

В 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 тогда и только тогда, когда я первична).

Пожилым неправильная версия

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