Вокруг задачи о числах Софи Жермен

Очень непростая задача в первую очередь в смысле чисто математическом -- и, как следствие, с точки зрения ее реализации в виде компьютерной программы. 


Коллега д-р Евгений Гогаевич Канель прислал очень четкий комментарий, который я ставлю в качестве отдельного поста, ибо оно того заслуживает.

Комментарий к решению задачи 1

Программа не выполняет предложенное

1. Для всех чисел Сен Жермен программа отвечает «ДА» - и это хорошо! 
2. Есть числа, которые НЕ являются числами Сен Жермен, но не смотря на это программа все равно отвечает «ДА» - а это уже плохо.

Пример: простое число a=71 НЕ является числом Сен Жермен, потому что b=2*a+1=143 = 11*13 не является простым числом. Однако программа ответит «ДА». 

Причина, разумеется, в том, что проверка на делимость (точнее, на неделимость)  на 2,3,5,7  является НЕОБХОДИМЫМ, но отнюдь не ДОСТАТОЧНЫМ условием того, чтобы число было простым. 

К примеру, число 121=11*11, очевидно, не делится ни на 2, ни на 3,5 или 7, однако, также очевидно, простым не является

Числа, на которые программа n1 ответит «ДА»

 11 23 29 41 53 71 83 89 113 131 149 173 179 191 209 221 233 239 251 263 281 293 299 323 341 359 383 389 401 419 431 443 449 461 473 491 503 509 533 551 569 593 599 611 629 641 653 659 671 683 701 713 719 743 761 779 803 809 821 839 851 863 869 881 893 911 923 929 953 971 989 1013 1019 1031 1049 1061  1073 1079 1091 1103 1121 1133 1139 1163 1181 1199 1223 1229 1241 1259 1271 1283 1289 1301 1313 1331 1343 1349 1373 1391 1409 1433 1439 1451 1469 1481 1493 1499 1511 1523 1541 1553 1559 …

Истинные числа Сен-Жермен

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559 ….

Решение д-ра Канеля

import java.util.*;

class n1_1

{ 

static Scanner reader=new Scanner(System.in); 

public static void main(String[] args)

{

  for(int i=1; i<1000; i++)

  {

    int x=6*i-1;

    if(x%2!=0 && x%3!=0 && x%5!=0 && x%7!=0)

    {

      int y=2*x+1;

      if(y%2!=0&& y%3!=0 && y%5!=0 && y%7!=0)

        System.out.print(x+" ");

    }

   

  }

   System.out.println();

}

}