Наибольший Простой Делитель решетом эратосфена - 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; }
Объяснение кода листинга программы
- Ввод числа с помощью функции scanf.
- Если число отрицательное, то умножаем его на -1.
- Выделяем память под массив чисел с помощью функции malloc.
- С помощью функции memset устанавливаем все элементы массива равными 1.
- Устанавливаем значения первых двух элементов массива равными 0.
- С помощью цикла for начинаем проверку всех чисел от 2 до n на делимость на числа, стоящие в массиве numbers.
- Если число делится на текущее число без остатка, то с помощью цикла for устанавливаем все его кратные значения в массиве numbers равными 0.
- С помощью цикла for начинаем проверку всех чисел от n до 1 на делимость на числа, стоящие в массиве numbers.
- Если число делится на текущее число без остатка и стоит в массиве numbers равным 1, то выводим это число и прерываем цикл.
- Освобождаем память, выделенную под массив чисел.
- Возвращаем 0, заканчивая работу программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д