Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Perl: Системное программирование > Программа по нахождению простых чисел...


Автор: Luck_brt 7.9.2007, 11:23
Доброго времени суток, вам.

Проблема такая,  начал недавно изучать язык Perl. И сталкнулся с проблемой. Есть код (был в мануале smile)) Вот, а мне надо его модифицировать, что бы он был правильным. И я никак не могу с этим справиться, вот решил обратиться за помощью к вам. Т.к. буду еще не раз писать, то создаю тему.
Заранее очень благодарин. Ниже код.

#!/usr/bin/perl -w

$maxprimes=20;
$value=1;
$count=0;

while ($count<$maxprimes) {
    $value++;
    $compasite=0;
OUTER:    for ($i=1;$i<$value ;$i++) {
        for ($j=1;$j<$value ;$j++) {
            if (($i*$j)==$value) {
                $compasite=1;
                last OUTER;
            }
        }
    }
if (1==$compasite) {
    $count++;
    print "$value ";
  }
}



P.S. Я думаю не то что я не могу найти вызод из ситуаци потому что у меня не хватает мозгов, я думаю потому что я еще токо знаю азы интерпретатора Perl. (Но это сугубо мое мнение smile))

Автор: amg 7.9.2007, 12:01
Да... 
Заменить 1==$compasite на 1!=$compasite, и будут печататься не составные, а простые числа.

Автор: Luck_brt 7.9.2007, 13:48
Цитата(amg @ 7.9.2007,  12:01)
Да... 
Заменить 1==$compasite на 1!=$compasite, и будут печататься не составные, а простые числа.

Спасибо!!! Слушай пожалсто, если будет время напиши, как так ???? ))) Нифига не могу догнать, даже когда ответ вот он... (((

Автор: Luck_brt 10.9.2007, 05:48
Прошу Вас кому не тяжело, напишите, почему, так ???

Автор: apook 10.9.2007, 07:40
анализ кода показал что сей код делает следующее:
1. воспроизводит числа от 0 до 20-и но цифру 20 можно поменять хоть на какую
2. далее походу воспроизведения каждого числа это число он отсчитывает с 1 до этого числа т.е если 4 то 1 2 3 4  при это по ходу уже этого счета каждое число он пытается перемножить со всеми читслами из которых он состоит т.е если это число 4 то будет так
Цитата

1*1   1*2   1*3
2*1   2*2   2*3
3*1   3*2   3*3

причем сама четверка не учавствует в умножении странным образом  т.е не будет действия 1*4 потому что условие сравнения такое
Код

if( $i<$value ) 

а не
Код

if( $i<=$value ) 


при этом каждое полученное число будет проверяеться на равенство 4 и если хоть один раз оно было равно 4-ем то получается(если программа правильная) это составное число...

От сюда вывод что этот код составными считает те которые можно получить из чисел из которых состоит это чисо путем уиножения smile пример в числе 4 при его разложении есть числа 1 2 3 4 (саму четверку не берем) теперь можно увидеть что 4 можно получить  2*2 так что прога говорит что это число годится , теперь берем число 3 оно состоит из 1 2 3 три не берем и  ни 1*2 ни 2*1 не дает 3 и прога его не считает составным

Воооот может разберешься, а может наоборот запутаешься???

Кстати я не понял значение строчки
Код

OUTER:

и
Код

last OUTER;


вот тот-же вариант без этих строчек
Код

#!/usr/bin/perl -w

for( $count=0,$value=1; $count<20; $value++ )
{
    $compasite=0;

    for( $i=1; $i<$value; $i++ )
    {
        for( $j=1; $j<$value; $j++ )
        { 
            if( ($i*$j)==$value )
            {
                $compasite=1;
                }
            }
        }

    if( $compasite==1 )
    {
        $count++;
        print "$value ";
       }
    }



Автор: Luck_brt 10.9.2007, 07:54
Нее, большое спасибо!!! Немного понял, не на все 100% но я пока токо 1раз прочитал smile Еще пару раз и ... Еще раз спасибо! было бы мне можно повышать репутацию , я бы с удовольствием повысел...
 А на счет этих строк, то просто, Вам ли незнать программирование это как искуство, каждый сочиняет как может smile

Автор: amg 10.9.2007, 10:37
Цитата(apook @  10.9.2007,  07:40 Найти цитируемый пост)
Кстати я не понял значение строчки OUTER: и last OUTER;
Ну это то ясно. Как только находится пара $i и $j такая, что ($i*$j)==$value, то значит, число $value - составное, дальше перебирать $i и $j не имеет смысла, и переходим к следующему $value. Это экономит время счета (если вообще можно говорить об экономии при таком алгоритме).

Автор: apook 10.9.2007, 10:37
Осторожно, здесь что-то не то!

Простое число это то число которое имеет ровно два натуральных делителя единицу и саму себя (см. http://ru.wikipedia.org/wiki/Простое_число)....

Я внес изменеия в предыдущий пост, добавил неразберихи, то что я обьяснял сперва это был поиск составных чисел, далее как сказал amg, меняем == на != и получаем поиск каких то других чисел(вродь получается что простых)

Извини за путанницу

Автор: Luck_brt 11.9.2007, 05:55
Теперь опять что то не так... Почему (1==$compasite) выдает составные а (1!=$compasite) выдает уже простые числа ??? я так понимаю что $compasite не равно 1-му то просто $count увеличеваеться и соответсвенно увеличиваеться счетчик найденых чисел. Но я так и непойму как $compasite обозначает что число являеться простым ? То что там перебираеться и переумножаеться, это тоже понятно. Но причем тут $compasite так и не понятно...

Автор: apook 11.9.2007, 06:45
Слухай сюда: 
Код
$compasite=1;
 делается тока тогда когда соблюдено условие 
Код
if( ($i*$j)==$value )
 а это условие означает что число составное так? так... по хорошему надо в этот момент выпрыгивать из циклов
Код

    for( $i=1; $i<$value; $i++ )
    {
        for( $j=1; $j<$value; $j++ )
        { 
            if( ($i*$j)==$value )
            {
                $compasite=1; #запомнили что это число составное
                }
            }
        }

так как уже следующие вычисления уже лишние, те к примеру строки
Код

OUTER:
и
last OUTER;

эту проблему как раз и решали(я просто новичек в Perl сразу не вьехал)
Далее идет проверка
Код

    if( $compasite==1 ) #если true то печатаем и увеличиваем счетчик
    {
        $count++;
        print "$value ";
       }

Стало быть изначально код предназначен находить сосавные числа, [для справки составное число это число не являющееся простым, Каждое составное число является произведением двух натуральных чисел больших 1], так если мы меняем == на != получаяется что производится поиск не таких чисел и если составное число это число не являющееся простым то не такое число это 
то число являющееся простым. Вот тока исходя из этого походу!

Автор: varnie 27.9.2007, 07:00
Код

perl -wle '(1 x $_) !~ /^(11+)\1+$/ && print while ++ $_'


забыл добавить, это решение официально расписано вhttp://ru.wikipedia.org/wiki/Perl

Автор: fantome 27.9.2007, 07:55
varnie, 
но это решение не эффективно по памяти, как там сказано... Но красивое не спорю... +1

а если надо написать прогу, которая будет искать простые числа - то лучше сначала покопаться в алгоритмах...

По крайней мере проверку на деление можно вести не до самого числа, а до корня квадратного из него... И много еще чего можно придумать... В свое время я на си реализовывал алгоритм генерации простых чисел для ЭЦП ГОСТ Р 34.10, пардон конечно за отступление от темы...

строчка
Код

last OUTER;

перебрасывает выполнение на последнюю строку цикла... насколько мне известно... то есть перебор продолжится дальше для новых значений $i , но значение $compasite уже установили в 1... А его сброс в 0 идет перед первым циклом for.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)