Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Простое число Вифериха / 22 сообщений из 22, страница 1 из 1
08.01.2014, 21:43
    #38519899
maximusend
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простое число Вифериха
Приветствую, господа!

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

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

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

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

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

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

Просто мысль)
...
Рейтинг: 0 / 0
10.01.2014, 19:19
    #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
10.01.2014, 19:37
    #38522488
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простое число Вифериха
maximusend, окей. Теперь посчитай среднюю скорость. Когда ты достигнешь 72 * 10^15 используя Java и BigInteger.
Ведь поиск новых чисел У. является целью. Не так ли?

Старые 1093 и 3511 нам уже неинтересны.
...
Рейтинг: 0 / 0
10.01.2014, 21:19
    #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
11.01.2014, 14:27
    #38522931
maximusend
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простое число Вифериха
Aleksandr SharahovПрограммист сделает это без BigInteger.
Можно поподробнее?
...
Рейтинг: 0 / 0
11.01.2014, 16:09
    #38522974
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простое число Вифериха
maximusendAleksandr SharahovПрограммист сделает это без BigInteger.
Можно поподробнее?
Ты посчитал скорость генерации и проверки чисел, хвастун?
...
Рейтинг: 0 / 0
11.01.2014, 16:31
    #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
11.01.2014, 16:45
    #38522991
wst
wst
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простое число Вифериха
Нельзя это в таком виде пробовать, потому как dividend при таком цикле будет расти как 0, 1, 3, 7, 15, 31 , тут надо просто удваивать его, а единицу вычитать уже при окончательном сравнении.
...
Рейтинг: 0 / 0
11.01.2014, 16:52
    #38522996
wst
wst
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простое число Вифериха
таки поспешил, сорри
...
Рейтинг: 0 / 0
11.01.2014, 16:54
    #38522998
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простое число Вифериха
wstНельзя это в таком виде пробовать, потому как dividend при таком цикле будет расти как 0, 1, 3, 7, 15, 31 , тут надо просто удваивать его, а единицу вычитать уже при окончательном сравнении.

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

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