powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Простое число Вифериха
22 сообщений из 22, страница 1 из 1
Простое число Вифериха
    #38519899
maximusend
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Приветствую, господа!

Есть задача: найти и вывести все простые числа Вифериха (Wieferich) .

Реализую на C#.

Формула, вроде как, простая: находим простое число и проверяем его на число Вифериха по формуле
Код: plaintext
(Math.Pow(2, i - 1) - 1) % (i * i) == 0
, но чего то не получается. Может просто числа слишком большие с экспонентой и он не может поделить их без остатка?

P. S. Простые числа находятся верно. Проблема именно с данным фрагментом.
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38519930
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Math.Pow работает с Double - тут ни размера, ни точности недостаточно.
Тут надо использовать сверхдлинную математику.
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38519935
maximusend
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Akina, это вообще возможно реализовать средствами C#?
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38519936
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ответ прост - 1093 и 3511
К декабрю 2012-ого года достиг предела поиска 72·10 15 и поиск продолжается.Вычисление "в лоб" потребует вычислений с числами, имеющими более 2 58 двоичных разрядов.
На 4 ТБ HDD умещается число размером всего лишь 2 45 двоичных разрядов.
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38519954
maximusend
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
А есть ли вообще какие-либо способы найти эти два числа? Что то беглый взгляд в сети никаких формул не выявил. Если это задание по программированию, то подразумевалось что решение есть же?
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38520015
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maximusendЕсли это задание по программированию, то подразумевалось чтоЕсли это задание по программированию, то подразумевается, что либо вы не будете решать его "в лоб" (воспользуетесь соответствующими математическими методами), либо освоите библиотеку для "длинных" вычислений.

Свежая ссылка на тему - habrahabr.ru/post/207754/
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38520580
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
miksoftОтвет прост - 1093 и 3511
К декабрю 2012-ого года достиг предела поиска 72·10 15 и поиск продолжается.Вычисление "в лоб" потребует вычислений с числами, имеющими более 2 58 двоичных разрядов.
На 4 ТБ HDD умещается число размером всего лишь 2 45 двоичных разрядов.
Подобные задачи ставят перед собой университеты с упором на математику. И обладающие
своими площадками для распределённых вычислений. И кустарю-одиночке с C#-ом там
делать нечего. Не та весовая категория. Хотя поковырять теорему Ферма всегда интересно.
Но опять-же со стороны математики на не long-digit-libraries.
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38521137
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maximusend,

вот когда ты в школе столбиком число делил, разве ты на каждом шагу сразу со всеми разрядами числа работал?

Просто мысль)
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522471
maximusend
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton, надо сказать, что данный вуз явно не заточен под математику и это обычная контрольная работа по программированию.

miksoft, выражаю персональную благодарность. Отличная ссылка. Задача решена. Код конечно корявый, но своё дело делает:

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
BigInteger wie, mult;
if (IsSimple) //если число простое
 {
   wie = 2; //по формуле
   wie = BigInteger.Pow(wie, i - 1); //возводим в степень
   wie = BigInteger.Subtract(wie, BigInteger.One); //от возведённого числа отнимаем единицу
   mult = BigInteger.Multiply(i, i); //по формуле
   if (BigInteger.Remainder(wie, mult) == 0) //если остатка при делении нет, значит число Вифериха
     //вывести число на экран
 }
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522488
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maximusend, окей. Теперь посчитай среднюю скорость. Когда ты достигнешь 72 * 10^15 используя Java и BigInteger.
Ведь поиск новых чисел У. является целью. Не так ли?

Старые 1093 и 3511 нам уже неинтересны.
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522563
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maximusendКод конечно корявый, но своё дело делает:

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
BigInteger wie, mult;
if (IsSimple) //если число простое
 {
   wie = 2; //по формуле
   wie = BigInteger.Pow(wie, i - 1); //возводим в степень
   wie = BigInteger.Subtract(wie, BigInteger.One); //от возведённого числа отнимаем единицу
   mult = BigInteger.Multiply(i, i); //по формуле
   if (BigInteger.Remainder(wie, mult) == 0) //если остатка при делении нет, значит число Вифериха
     //вывести число на экран
 }



Программист сделает это без BigInteger.
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522931
maximusend
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Aleksandr SharahovПрограммист сделает это без BigInteger.
Можно поподробнее?
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522974
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maximusendAleksandr SharahovПрограммист сделает это без BigInteger.
Можно поподробнее?
Ты посчитал скорость генерации и проверки чисел, хвастун?
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522985
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maximusendAleksandr SharahovПрограммист сделает это без BigInteger.
Можно поподробнее?

В качестве отправной точки для последующей оптимизации можно попробовать это

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
function IsWieferichNumber(Number: integer): boolean;
var
  Dividend, Divisor: integer;
begin;
  Divisor:=Number*Number;
  Dividend:=0;
  dec(Number);
  repeat;
    Dividend:=Dividend+Dividend+1;
    if Dividend>=Divisor then Dividend:=Dividend-Divisor;
    dec(Number);
    until Number<=0;
  Result:=(Dividend=0);
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: integer;
begin;
  for i:=1 to $7FFF do if IsWieferichNumber(i) then Memo1.Lines.Add(IntToStr(i));
  Memo1.Lines.Add('done');
  end;
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522991
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нельзя это в таком виде пробовать, потому как dividend при таком цикле будет расти как 0, 1, 3, 7, 15, 31 , тут надо просто удваивать его, а единицу вычитать уже при окончательном сравнении.
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522996
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
таки поспешил, сорри
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38522998
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
wstНельзя это в таком виде пробовать, потому как dividend при таком цикле будет расти как 0, 1, 3, 7, 15, 31 , тут надо просто удваивать его, а единицу вычитать уже при окончательном сравнении.

А результат будет сильно отличаться? ))
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38523002
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Просто дошло когда нажимал "отправить".
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38687469
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
miksoftОтвет прост - 1093 и 3511
На 4 ТБ HDD умещается число размером всего лишь 2 45 двоичных разрядов.

почему ? я думал 2^50
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38687496
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
miksoftОтвет прост - 1093 и 3511
К декабрю 2012-ого года достиг предела поиска 72·10 15 и поиск продолжается.Вычисление "в лоб" потребует вычислений с числами, имеющими более 2 58 двоичных разрядов.
На 4 ТБ HDD умещается число размером всего лишь 2 45 двоичных разрядов.Вообще-то чтобы вычислить a^b%M, достаточно всего в два раза больше разрядов чем в M. Всего каких-то 256 разрядов хватит :)
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38687503
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
...
Рейтинг: 0 / 0
Простое число Вифериха
    #38687521
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
maximusendmayton, надо сказать, что данный вуз явно не заточен под математику и это обычная контрольная работа по программированию.

miksoft, выражаю персональную благодарность. Отличная ссылка. Задача решена. Код конечно корявый, но своё дело делает:

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
BigInteger wie, mult;
if (IsSimple) //если число простое
 {
   wie = 2; //по формуле
   wie = BigInteger.Pow(wie, i - 1); //возводим в степень
   wie = BigInteger.Subtract(wie, BigInteger.One); //от возведённого числа отнимаем единицу
   mult = BigInteger.Multiply(i, i); //по формуле
   if (BigInteger.Remainder(wie, mult) == 0) //если остатка при делении нет, значит число Вифериха
     //вывести число на экран
 }


как-то так: if (BigInteger.PowMod(2, i-1, i*i) == 1) вывести число на экран
...
Рейтинг: 0 / 0
22 сообщений из 22, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Простое число Вифериха
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]