За последние 24 часа нас посетил 14831 программист и 1728 роботов. Сейчас ищут 722 программиста ...

Решето Эратосфена

Тема в разделе "Решения, алгоритмы", создана пользователем Alesto, 7 мар 2017.

  1. Alesto

    Alesto Новичок

    С нами с:
    15 янв 2017
    Сообщения:
    72
    Симпатии:
    8
    Всем привет, есть задачка которая немного в какой то мере заставила задуматься ( как начинающего ).
    Вот решение, алгоритм насколько я знаю известный поэтому без комментов, если будет необходимо добавлю.

    PHP:
    1. $s = array_fill(2, 200 - 1,true);
    2. $sum = 0;
    3.  
    4. for ($i = 2; $i <= 200; $i++) {
    5.   if ($s[$i] === true) {
    6.     for ($j = $i * $i; $j <= 200; $j += $i) {
    7.       $s[$j] = false;
    8.     }
    9.   }
    10. }
    11.  
    12. foreach ($s as $key => $value) {
    13.   if ($value === true) {
    14.     $sum += $key * $key;
    15.   }
    16. }
    17.  
    18. echo "Сумма простых чисел: $sum";
    А завис я от смысла "сумму произведений всех простых чисел на их порядковые номера". Ведь судя по этому алгоритму порядковым номером (индексом) и является простое число которое нашли.
    PHP:
    1. $sum += $key * $key;
    Друзья, все ли я правильно понял?
     
  2. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.156
    Симпатии:
    1.770
    Адрес:
    :сердА
    Нет, неправильно.
    Если порядковый номер $key, а число $value, то произведение числа на порядковый номер
    $value*=$key;
    И это дело прибавить к $sum

    В то время как у тебя считается сумма квадратов ключей.
     
    Alesto нравится это.
  3. Alesto

    Alesto Новичок

    С нами с:
    15 янв 2017
    Сообщения:
    72
    Симпатии:
    8
    У нас первым делом заполняется массив с числами от 2 до 200 по порядку.
    После в цикле каждому индексу дается значение true, после которого вычисляется простое оно или нет.
    Вот и получается у нас список где оставшиеся ключи с значение true (которое говорит о том, что число простое).
    Где ключ он же порядковый номер он же простое число.

    Разве не так?

    P.s. алгоритм брал с https://habrahabr.ru/post/133037/
     
  4. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.156
    Симпатии:
    1.770
    Адрес:
    :сердА
    Окей, я не вдавался в ваш код, но не важно, откуда вы его брали.

    Сказано, сумма произведений чисел на порядковые номера. Подключаем здравый смысл:

    Есть простые числа: 1 3 5 7 11 13 17 19
    Есть их порядковые номера 0 1 2 3 4 5 6 7 ну или 1 2 3 4 5 6 7 8.
    И, следовательно, ожидается сумма произведений:
    1*1
    2*3
    3*5
    4*7 и тд.
     
    #4 Fell-x27, 7 мар 2017
    Последнее редактирование: 8 мар 2017
    Alesto нравится это.
  5. Alesto

    Alesto Новичок

    С нами с:
    15 янв 2017
    Сообщения:
    72
    Симпатии:
    8
    Я понял свою ошибку, спасибо.