Генерация простых чисел

Форум пользователей пакета Maple

Модератор: Admin

Elena212
Сообщения: 20
Зарегистрирован: Чт май 20, 2010 10:33 am

Генерация простых чисел

Сообщение Elena212 » Вт окт 26, 2010 4:00 pm

Добрый день.
Столкнулась с такой задачей. Не могу разобраться как сгенерировать простые числа. Вот такое условие:

Подсчитать количество простых 10значных чисел, в записи которых нет одинаковых цифр

Понимаю, что процедура не должна быть сложной, но не могу сообразить как это сделать. Не могли бы помочь?

xyz
Сообщения: 202
Зарегистрирован: Чт мар 24, 2005 3:42 pm

Сообщение xyz » Вт окт 26, 2010 7:41 pm

> Test := proc(m::posint)
local a, b, c;
a, b := 0, 0;
do
a := a + 1;
c := length(a);
if m < c then return b
elif type(a, prime) and
nops({op(convert(cat("", a), list))}) = c then
b := b + 1
end if
end do
end proc;


> Test(5);
3160

xyz
Сообщения: 202
Зарегистрирован: Чт мар 24, 2005 3:42 pm

Сообщение xyz » Вт окт 26, 2010 8:51 pm

Несколько более быстрая процедура


> Test1 := proc(m::posint)
local a, b, c, d;
a, d := 0, 0;
do
a := a + 1;
b := ithprime(a);
c := length(b);
if m < c then return d
elif nops({op(convert("" || b, list))}) = c then
d := d + 1
end if
end do
end proc;

> Test1(6);
13399

xyz
Сообщения: 202
Зарегистрирован: Чт мар 24, 2005 3:42 pm

Сообщение xyz » Вт окт 26, 2010 9:27 pm

Прошу извинить, но пкрвые 2 процедуры решают несколько иную задачу - находят все простые числа требуемого свойства с длиной не более 10. Ниже то, что вам нужно

> Test2 := proc(m::posint)
local a, b, c;
a, b := 10^(m - 1), 0;
do
a := a + 1;
c := length(a);
if m < c then return b
elif type(a, prime) and
nops({op(convert("" || a, list))}) = c then
b := b + 1
end if
end do
end proc;


> Test2(6);
10239

xyz
Сообщения: 202
Зарегистрирован: Чт мар 24, 2005 3:42 pm

Сообщение xyz » Вт окт 26, 2010 11:46 pm

Более быстрая процедура на основе предыдущей.

> Test3 := proc(m::posint)
local a, b, c;
a, b := nextprime(10^(m - 1)), 0;
do
c := length(a);
if m < c then return b
elif nops({op(convert("" || a, list))}) = c then
b := b + 1
end if;
a := nextprime(a)
end do
end proc:


> Test3(6);
10239

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Re: Генерация простых чисел

Сообщение Kitonum » Ср окт 27, 2010 12:38 am

Elena212 писал(а):Добрый день.
Столкнулась с такой задачей. Не могу разобраться как сгенерировать простые числа. Вот такое условие:

Подсчитать количество простых 10значных чисел, в записи которых нет одинаковых цифр

Понимаю, что процедура не должна быть сложной, но не могу сообразить как это сделать. Не могли бы помочь?

А задачка то оказалась весьма поучительной, можно даже сказать прикольной! Расскажу вкратце как я её решал.
Вначале я написал процедуру, основанную, как и процедура xyz, на переборах возможных вариантов. Только моя процедура решает несколько более общую задачу: она выдаёт список всех простых чисел с различными цифрами в диапазоне от N1 до N2 включительно и их число. Вот код процедуры (может кому-нибудь окажется полезной):
P:=proc(N1,N2)
local a,b,c,L,i,M:
a:=nextprime(N1-1):
b:=prevprime(N2+1):
L:=[a]:
for i from 1 while L[nops(L)]<=b do
c:=convert(L[nops(L)],string):
if nops([seq(c[k],k=1..length(c))])=nops({seq(c[k],k=1..length(c))}) then
L:=[op(L),nextprime(L[nops(L)])] else L:=[op(subsop(nops(L)=NULL,L)),nextprime(L[nops(L)])]: fi:
od:
M:=subsop(nops(L)=NULL,L):
M, nops(M);
end proc:


Пример работы:
P(100,999);
[103, 107, 109, 127, 137, 139, 149, 157, 163, 167, 173, 179, 193,

197, 239, 241, 251, 257, 263, 269, 271, 281, 283, 293, 307,

317, 347, 349, 359, 367, 379, 389, 397, 401, 409, 419, 421,

431, 439, 457, 461, 463, 467, 479, 487, 491, 503, 509, 521,

523, 541, 547, 563, 569, 571, 587, 593, 601, 607, 613, 617,

619, 631, 641, 643, 647, 653, 659, 673, 683, 691, 701, 709,

719, 739, 743, 751, 761, 769, 809, 821, 823, 827, 829, 839,

853, 857, 859, 863, 907, 937, 941, 947, 953, 967, 971, 983],

97


Понятно, что с помощью данной процедуры решить поставленную задачу Подсчитать количество простых 10значных чисел, в записи которых нет одинаковых цифр за разумное время проблематично, ведь диапазон от 1000000000 до 9999999999 содержит 9 миллиардов чисел.
Потом только сообразил, что т.к. цифр всего 10 (от 0 до 9), то в десятизначном числе каждая цифра может встретиться только 1 раз, поэтому достаточно сгенерировать всевозможные перестановки, не начинающиеся с 0, из этих цифр и далее проверять на простоту только числа, образованные этими перестановками. Таких чисел будет 9*9!=3265920.
Вот программа, основанная на этой идее:
L:=[]:
for i from 1 to 9 do
M:=combinat[permute]([op({seq(k,k=0..9)} minus {i})]):
L:=[op(L),seq([i,op(M[j])],j=1..nops(M))]:
od:
L1:=[]:
for j from 1 to nops(L) do
a:=add(10^(10-k)*L[j][k],k=1..10):
if isprime(a) then
L1:=[op(L1),a]: fi:
od:
nops(L1);


Программа проработала где-то в пределах получаса и выдала результат: 0, т.е. таких простых вообще не существует!
И только после этого до меня дошло, что этот результат очевиден с самого начала без всяких программ: сумма всех целых чисел от 0 до 9 равна 45, т.е. признак делимости на 3 даёт, что такое десятизначное число не может быть простым!

Elena212
Сообщения: 20
Зарегистрирован: Чт май 20, 2010 10:33 am

Сообщение Elena212 » Ср окт 27, 2010 11:14 am

Огромное спасибо, вы мне очень помогли!

sidor
Сообщения: 41
Зарегистрирован: Пн дек 22, 2008 7:37 pm

Сообщение sidor » Ср окт 27, 2010 8:29 pm

Изменим условие задачи:
Подсчитать количество простых 9-значных чисел, в записи которых нет одинаковых цифр и отсутствует цифра 2.
Как нужно изменить процедуру для этого случая?

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Ср окт 27, 2010 9:45 pm

sidor писал(а):Изменим условие задачи:
Подсчитать количество простых 9-значных чисел, в записи которых нет одинаковых цифр и отсутствует цифра 2.
Как нужно изменить процедуру для этого случая?

Находим число таких простых:
L:=[]:
for i in [1,3,4,5,6,7,8,9] do
M:=combinat[permute]([op({seq(k,k=[0,1,3,4,5,6,7,8,9])} minus {i})]):
L:=[op(L),seq([i,op(M[j])],j=1..nops(M))]:
od:
L1:=[]:
for j from 1 to nops(L) do
a:=add(10^(9-k)*L[j][k],k=1..9):
if isprime(a) then
L1:=[op(L1),a]: fi:
od:
nops(L1);


26455

Вот первая сотня таких простых:
seq(L1[i],i=1..100);
103456789, 103458679, 103458967, 103468759, 103468957, 103478569,

103478659, 103485769, 103486759, 103495687, 103546879,

103564897, 103564987, 103567489, 103568749, 103574869,

103576849, 103578469, 103578649, 103584769, 103584967,

103589467, 103594867, 103645879, 103645987, 103648957,

103649587, 103659847, 103674589, 103684579, 103684597,

103685947, 103687459, 103698547, 103754869, 103768549,

103785469, 103845769, 103846579, 103846597, 103849567,

103854697, 103856497, 103856749, 103864759, 103865479,

103865947, 103869457, 103869547, 103875649, 103895647,

103948567, 103948657, 103956487, 103958467, 103964587,

103965487, 103968547, 103985647, 104358769, 104359687,

104359867, 104368597, 104369857, 104386759, 104389657,

104537689, 104538769, 104568379, 104568397, 104569837,

104578963, 104579863, 104586379, 104586973, 104587963,

104589673, 104596783, 104596837, 104596873, 104635789,

104635897, 104635987, 104637859, 104638759, 104638957,

104653897, 104658397, 104658793, 104659783, 104659873,

104673859, 104675839, 104679853, 104685937, 104695783,

104698357, 104736589, 104756389, 104758639


xyz
Сообщения: 202
Зарегистрирован: Чт мар 24, 2005 3:42 pm

Сообщение xyz » Ср окт 27, 2010 11:17 pm

Процедура приведена ниже. Правда, увидел уже решение, но решил привести и свое, использующее лишь базовые средства. Я уже и не рад, что ввязался в эту задачку, ниже станет яснее почему.

> Test4 := proc(m::posint)
local a, b, c, d;
a, b := nextprime(10^(m - 1)), 0;
do
c := length(a);
if m < c then return b
else
d := convert("" || a, list);
if nops({op(d)}) = c and not member("2", d) then
b := b + 1
end if;
a := nextprime(a)
end if
end do
end proc
> Test4(9);
26455

Но в этой связи возникают вот какие мысли. Сам я читаю математику студентам, Maple и Mathematica студентам и магистрантам. Задачи такого типа, как правило, даются студентам, изучающим эти пакеты. Но тут возникает вопрос по таким задаче. Когда я давал эффективное решение первой задачи, то проверка ее при N=6 уже показала временные издержки. А число N=10 сразу же навело на мысль использовать признаки делимости, которые для кортежей длины 10 из цифр 0..9 без повторов показывают, что они удовлетворяют признакам делимости на 3 и 9. Они известны даже школьникам. После чего проверил процедуру при N=10 и в фоновом режиме потребовалось чуть более 20 мин.

Поэтому возникает вопрос: либо преподаватель сам не ведал, что дает, либо решил покуражиться. А ведь запрограммировать и протестировать алгоритм можно было уже на N=4..6. А то было предложено для крайнего случая, ибо для N>=10 при поставленных условиях процедура будет всегда возвращать 0. Вот и ваша процедура из той же оперы, когда ожидание результата выполнения не соизмеримы с затратами на программирование. Не совсем понятно, что дают подобные задачи для освоения программирования в пакете.

В этом случае рекомендую Mathematica. У обоих пакетов свои «+» и «-», но Mathematica намного более реактивна. Впрочем, у каждого свой вкус. На эту тему можно говорить много, но нет времени. И так задержался на этом форуме непозволительно долго.

> for k to 8 do time(assign('T'=Test3(k))), T end do;
0.0, 4
0.0, 20
0.0, 97
0.078, 510
0.704, 2529
6.890, 10239
79.844, 33950
775.063, 90510

Test3[m_]:=Module[{a, b, c}, a:=NextPrime[10^(m-1)-1]; b:= 0;
c := Length[IntegerDigits[a]];
While[c==m, a=NextPrime[a]; c:=Length[IntegerDigits[a]];
If[m==Length[DeleteDuplicates[IntegerDigits[a]]],b=b+1,Null]];b]

k = 1; While[k != 9, Print[Timing[Test3[k]]]; k++]
{0.0, 4}
{0.0, 20}
{0.0, 97}
{0.078, 510}
{0.5, 2529}
{4.312, 10239}
{46.203, 33950}
{401.094, 90510}

И последнее. Я как-то уже говорил, что не совсем уместно решать задачи на студфоруме за студентов. Разве что для самоутверждения. Другое дело разъяснять тонкости пакета, его особенности, разбирать отдельные сложные конструкции, а так решать задачки, ну уж просто какая-то узаконенная шпаргалка. Рекомендую посмотреть форум www.mapleprimes.com, на котором превалирует именно отмеченная идеология. Ведь не зря же его не чураются и сами разработчики. Хотелось бы видеть настоящий форум именно таким, тогда и придут на него серьезные пользователи.

Edik
Сообщения: 31
Зарегистрирован: Пн мар 22, 2010 3:24 pm

Сообщение Edik » Пт окт 29, 2010 1:55 pm

Здравствуйте.
А как сделать, чтобы в задаче про простые десятизначные числа, выводилось не только их количество, но и сами сгенерированные числа с их простым делителем?

Edik
Сообщения: 31
Зарегистрирован: Пн мар 22, 2010 3:24 pm

Сообщение Edik » Пт окт 29, 2010 2:00 pm

В том смысле, что к каждому числу один простой делитель.

sidor
Сообщения: 41
Зарегистрирован: Пн дек 22, 2008 7:37 pm

Сообщение sidor » Пт окт 29, 2010 2:03 pm

Процедура kitonum решила задачу за 74 сек. Программа xyz трудилась 1 час 12 минут, т.е. она построена на методе дурного перебора. Г-н xyz не решил задачу как математик и очень плохо выполнил ее как программист.
Поэтому трудно представить, как он может "разъяснять тонкости пакета, его особенности, разбирать отдельные сложные конструкции". И длинное непонятное послесловие написано, видимо, чтобы скрыть свою неудачу.

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Пт окт 29, 2010 6:39 pm

Edik писал(а):Здравствуйте.
А как сделать, чтобы в задаче про простые десятизначные числа, выводилось не только их количество, но и сами сгенерированные числа с их простым делителем?

Уточните свой вопрос, а то просто непонятно, что Вы хотите! Если число простое, то у него всего 2 делителя - единица и само число.

Edik
Сообщения: 31
Зарегистрирован: Пн мар 22, 2010 3:24 pm

Сообщение Edik » Пт окт 29, 2010 7:14 pm

Kitonum писал(а):
Edik писал(а):Здравствуйте.
А как сделать, чтобы в задаче про простые десятизначные числа, выводилось не только их количество, но и сами сгенерированные числа с их простым делителем?

Уточните свой вопрос, а то просто непонятно, что Вы хотите! Если число простое, то у него всего 2 делителя - единица и само число.


Хотелось бы вывести на экран все числа, которые перебираем, и для каждого вывести хотя бы один их делитель. Чтобы доказать, что число непростое.
Как это сделать?