Как этот код работает для определения числа делителей числа?
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.
Слишком много недоразумений относительно этого подхода, может кто-нибудь объяснить весь алгоритм, как он работает.
Решение
-
Жесткий предел для массивов установлен, вероятно, потому что проблема требует этого? Если нет, то просто плохой код.
-
Внутри внутреннего цикла вы вычисляете наибольшую степень простого числа, которое делит число. Зачем? Смотри пункт 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 значения хранятся в массиве, чтобы знать, являются ли они простыми или нет.)
Другие решения