Страницы

Поиск по вопросам

вторник, 21 мая 2019 г.

Вычисление наибольшего простого делителя решетом Эратосфена

Когда х>996 отказывается работать, помогите пожалуйста. Собственно, код:
#include #include
int main() { int x, p, i, q, max, min; scanf ("%d", &x);
int *a = (int*)malloc(abs(x)+1 * sizeof(int));
for (i=0; i<=abs(x); i++) a[i] = i;
a[1]=0;
for (p=2; p<=abs(x); p++){ for (q=p*2; q<=abs(x); q+=p) a[q]=0; }
max=0;
if (x>=0){ for(i=0; i<=abs(x); i++) if((a[i]!=0) && (abs(x)%a[i]==0)) if (a[i]>max) max=a[i];
printf("%d", max); free(a); }
else{
min=abs(x);
for(i=0; i<=abs(x); i++) if((a[i]!=0) && (abs(x)%a[i]==0)) if (a[i]printf ("%d", -min); free(a); } }


Ответ

Не понимаю, что значат в этой программе отрицательные значения x, но в любом случае abs(x) вычислять надо 1 раз. Ошибка случается оттого, что вы выделяете память так
int *a = (int*)malloc(abs(x)+1 * sizeof(int));
а надо
int *a = (int*)malloc((abs(x)+1) * sizeof(int));
Код можно оптимизировать - максимальный делитель определить еще при построении решета.
#include #include #include
int main() { int x, p, i, q, max, min; scanf ("%d", &x); bool b=true; if (x<0) b=false;
x=abs(x); int *a = (int*)malloc((x+1) * sizeof(int));
for (i=0; i<=x; i++) a[i] = i;
a[1]=0; max=0; min=0; for (p=2; p<=x; p++){ if (a[p]==p) for (q=p*2; q<=x; q+=p) { a[q]=0; if(q==x) max=p; if(q==x&&min==0) min=p; } }
if (b){ printf("%d", max); free(a); }
else{ printf ("%d", -min); free(a); } _getch(); }

Комментариев нет:

Отправить комментарий