Наибольший Простой Делитель решетом эратосфена - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Здравствуйте. Выдали задание желающим реализовать поиск наибольшего простого делителя методом решета Эратосфена. Решето и Поиск протого делителя по отдельности реализовал, а вот соединить не получается. В попытках решить уже запутался, так как видимо алгоритм использую неправильно. Мой вариант работает для чисел примерно до 10 в 6 степени(дальше идет переполнение, не знаю как от него избавиться), а по заданию числа могут быть и больше
#include <stdio.h>
#include <math.h>
#define p 65536
int main()
{
    long long int i, j, k, h;
        long long int n;
   long long int  a[p], max;
    scanf ("%lli", &n);
    if (n<0) n=-1*n;
    h = (int) sqrt((double) n);
     //заполним решето и повычеркиваем что не надо
    for (j = 0; j <= h; j++) a[j] = j;
    a[1] = 0;
 
    for (i = 2; i <= p; i++) {        
        if (a[i] != 0) {
            for (k = i*2; k <= p; k = k + i) {
                a[k] = 0;
                                             }
                       }
                             }
    max = 0;
    for (i=0; i<=p; i++)
    {
            if(a[i] > max)
            {
                if (n % a[i] == 0) 
                max = a[i];
            }
    }
 
   if (max == 0) printf("%d", n);
   else printf("%d", max);
   return 0;
}

Решение задачи: «Наибольший Простой Делитель решетом эратосфена»

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
int main()
{
    long long n, i, j;
    char* numbers = NULL;
 
    scanf("%lli", &n);
    if( n < 0 ) n *= -1;
 
    numbers = (char*)malloc( n+1 );
    memset( numbers, 1, n+1 );
    numbers[0] = numbers[1] = 0;
 
    for( i = 2; i <= n; ++i )
    {
        if( numbers[i] )
        {
            for( j = i*2; j <= n; j += i )
            {
                numbers[j] = 0;
            }
        }
    }
 
    for( i = n; i > 0; --i )
    {
        if( numbers[i] && !(n % i) )
        {
            printf( "%d", i );
            break;
        }
    }
 
    free( numbers );
    return 0;
}

Объяснение кода листинга программы

  1. Ввод числа с помощью функции scanf.
  2. Если число отрицательное, то умножаем его на -1.
  3. Выделяем память под массив чисел с помощью функции malloc.
  4. С помощью функции memset устанавливаем все элементы массива равными 1.
  5. Устанавливаем значения первых двух элементов массива равными 0.
  6. С помощью цикла for начинаем проверку всех чисел от 2 до n на делимость на числа, стоящие в массиве numbers.
  7. Если число делится на текущее число без остатка, то с помощью цикла for устанавливаем все его кратные значения в массиве numbers равными 0.
  8. С помощью цикла for начинаем проверку всех чисел от n до 1 на делимость на числа, стоящие в массиве numbers.
  9. Если число делится на текущее число без остатка и стоит в массиве numbers равным 1, то выводим это число и прерываем цикл.
  10. Освобождаем память, выделенную под массив чисел.
  11. Возвращаем 0, заканчивая работу программы.

Оцени полезность:

11   голосов , оценка 3.545 из 5
Похожие ответы