Как этот код работает для определения числа делителей числа?

Question

Как этот код работает для определения числа делителей числа?

http://www.spoj.com/problems/NDIV/

Это постановка проблемы. Так как я новичок в программировании, эта конкретная проблема сорвала меня, я нашел этот конкретный код в Интернете, который, когда я пытался отправить, получил AC. Я хочу знать, как работает этот код, поскольку я представил его из онлайн-источника, что само по себе является плохой идеей для начинающих.

#include <bits/stdc++.h>
using namespace std;
int check[32000];
int prime[10000];
void shieve()
{
for(int i=3;i<=180;i+=2)
{
if(!check[i])
{
for(int j=i*i;j<=32000;j+=i)
check[j]=1;
}
}
prime[0] = 2;
int j=1;
for(int i=3;i<=32000;i+=2)
{
if(!check[i]){
prime[j++]=i;
}
}
}
int main()
{
shieve();
int a,b,n,temp,total=1,res=0;
scanf("%d%d%d",&a,&b,&n);
int count=0,i,j,k;
for(i=a;i<=b;i++)
{
temp=i;
total=1;
k=0;
for(j=prime[k];j*j<=temp;j=prime[++k])
{
count=0;
while(temp%j==0)
{
count++;
temp/=j;
}
total *=count+1;
}
if(temp!=1)
total*=2;
if(total==n)
res++;
}
printf("%d\n",res);
return 0;
}

Похоже, код работает на сите из эратосфена, но некоторые вещи я не могу понять.

Почему предел массива «проверка» составляет 32000?
Опять же, почему предел для простого массива равен 10000?
Внутри main, что бы ни происходило внутри цикла for j.

Слишком много недоразумений относительно этого подхода, может кто-нибудь объяснить весь алгоритм, как он работает.

-1

c++factors sieve-of-eratosthenes

Решение

Другие решения

Источник

Accepted Answer

Жесткий предел для массивов установлен, вероятно, потому что проблема требует этого? Если нет, то просто плохой код.
Внутри внутреннего цикла вы вычисляете наибольшую степень простого числа, которое делит число. Зачем? Смотри пункт 3.
Количество факторов числа n можно рассчитать следующим образом:

Пусть n = (p1) ^ (n1) * (p2) ^ (n2) …, где p1, p2 — простые числа, а n1, n2 … — их показатели. Тогда число факторов n = (n1 + 1) * (n2 + 1) …

Отсюда и линия total *= count + 1 что в основном total = total * (count + 1) (где count является наибольшим показателем простого числа, которое делит исходное число) вычисляет число простых множителей числа.

И да, в коде реализовано сито Эратосфена для хранения простых чисел в таблице.

(редактировать Только что увидел проблему — нужно как минимум 10 ^ 4 boolean значения для хранения простых чисел (вам на самом деле не нужно хранить значения, просто флаг, указывающий, являются ли значения простыми или нет). Условие дано 0 <= b - a <= 10^4 Итак, начните свой цикл с a в b и проверить на bool значения хранятся в массиве, чтобы знать, являются ли они простыми или нет.)

1