считать различные простые множители

Мне нужно подсчитать количество различных простых множителей от 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;
}

math prime-factoring number-theory
person alankrita    schedule 14.07.2013    source источник

Ответы (2)


arrow_upward
8
arrow_downward

Вы можете легко приспособить решето Эрастотена для подсчета количества простых множителей числа.

Вот реализация на 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;
}
person user2580621    schedule 14.07.2013
comment
Кстати, код в ответе от @v-delecroix работает неправильно (например, он сообщает, что 12345 имеет 4 различных простых множителя, когда их 3). (PS: я публикую это здесь из-за системы репутации SO) - person user2580621; 14.07.2013

arrow_upward
2
arrow_downward

Вы определенно можете добиться большего успеха, сделав сито из Эратосфена.

В Питоне

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
person V. Delecroix    schedule 14.07.2013
comment
Хорошо, но оператор запросил количество различных простых множителей. Например, число 4 имеет только один отличный простой делитель. - person President James K. Polk; 14.07.2013
comment
Поскольку все инициализируется в 1, это не очень хороший ответ... после @user2580621 я просмотрел свой код... - person V. Delecroix; 14.07.2013
comment
+1, выглядит очень красиво. Его можно сделать более эффективным, изменив первый цикл так, чтобы он останавливался на int(N0,5), а затем добавив последний цикл, который идет от int(N0,5) + 1 до N, который заменяет любые оставшиеся нули. с теми. - person President James K. Polk; 14.07.2013
comment
@GregS Большое спасибо за рабочий и красивый код! - person V. Delecroix; 14.07.2013
comment
N//2 больше, чем нужно. N**0,5 (что соответствует квадратному корню из N) достаточно. - person President James K. Polk; 15.07.2013