def PrimeSieve(curNum):
    prime = True
    del updateList[:]
    for cp in PrimeList:
        daPrime, daSkip = cp
        if curNum == daSkip:
            prime = False
            upcp = (daPrime, daSkip + daPrime)
            updateList.append(upcp)
        else:
            updateList.append(cp)
    if prime:
        updateList.append((curNum,2*curNum))
    return prime

PrimeList = []
updateList = []

for x in range(2, 1111):
    print(x, PrimeSieve(x))
    del PrimeList[:]
    for i in updateList:
        PrimeList.append(i)

2 True
3 True
4 False
5 True
6 False
7 True
8 False
9 False
10 False
11 True
12 False
13 True
14 False
15 False
16 False
17 True
18 False
19 True
20 False
21 False
22 False
23 True
24 False
25 False
26 False
27 False
28 False
29 True
30 False
31 True
32 False
33 False
34 False
35 False
36 False
37 True
38 False
39 False
40 False
41 True
42 False
43 True
44 False
45 False
46 False
47 True
48 False
49 False
50 False
51 False
52 False
53 True
54 False
55 False
56 False
57 False
58 False
59 True
60 False
61 True
62 False
63 False
64 False
65 False
66 False
67 True
68 False
69 False
70 False
71 True
72 False
73 True
74 False
75 False
76 False
77 False
78 False
79 True
80 False
81 False
82 False
83 True
84 False
85 False
86 False
87 False
88 False
89 True
90 False
91 False
92 False
93 False
94 False
95 False
96 False
97 True
98 False
99 False
100 False
101 True
102 False
103 True
104 False
105 False
106 False
107 True
108 False
109 True
110 False
111 False
112 False
113 True
114 False
115 False
116 False
117 False
118 False
119 False
120 False
121 False
122 False
123 False
124 False
125 False
126 False
127 True
128 False
129 False
130 False
131 True
132 False
133 False
134 False
135 False
136 False
137 True
138 False
139 True
140 False
141 False
142 False
143 False
144 False
145 False
146 False
147 False
148 False
149 True
150 False
151 True
152 False
153 False
154 False
155 False
156 False
157 True
158 False
159 False
160 False
161 False
162 False
163 True
164 False
165 False
166 False
167 True
168 False
169 False
170 False
171 False
172 False
173 True
174 False
175 False
176 False
177 False
178 False
179 True
180 False
181 True
182 False
183 False
184 False
185 False
186 False
187 False
188 False
189 False
190 False
191 True
192 False
193 True
194 False
195 False
196 False
197 True
198 False
199 True
200 False
201 False
202 False
203 False
204 False
205 False
206 False
207 False
208 False
209 False
210 False
211 True
212 False
213 False
214 False
215 False
216 False
217 False
218 False
219 False
220 False
221 False
222 False
223 True
224 False
225 False
226 False
227 True
228 False
229 True
230 False
231 False
232 False
233 True
234 False
235 False
236 False
237 False
238 False
239 True
240 False
241 True
242 False
243 False
244 False
245 False
246 False
247 False
248 False
249 False
250 False
251 True
252 False
253 False
254 False
255 False
256 False
257 True
258 False
259 False
260 False
261 False
262 False
263 True
264 False
265 False
266 False
267 False
268 False
269 True
270 False
271 True
272 False
273 False
274 False
275 False
276 False
277 True
278 False
279 False
280 False
281 True
282 False
283 True
284 False
285 False
286 False
287 False
288 False
289 False
290 False
291 False
292 False
293 True
294 False
295 False
296 False
297 False
298 False
299 False
300 False
301 False
302 False
303 False
304 False
305 False
306 False
307 True
308 False
309 False
310 False
311 True
312 False
313 True
314 False
315 False
316 False
317 True
318 False
319 False
320 False
321 False
322 False
323 False
324 False
325 False
326 False
327 False
328 False
329 False
330 False
331 True
332 False
333 False
334 False
335 False
336 False
337 True
338 False
339 False
340 False
341 False
342 False
343 False
344 False
345 False
346 False
347 True
348 False
349 True
350 False
351 False
352 False
353 True
354 False
355 False
356 False
357 False
358 False
359 True
360 False
361 False
362 False
363 False
364 False
365 False
366 False
367 True
368 False
369 False
370 False
371 False
372 False
373 True
374 False
375 False
376 False
377 False
378 False
379 True
380 False
381 False
382 False
383 True
384 False
385 False
386 False
387 False
388 False
389 True
390 False
391 False
392 False
393 False
394 False
395 False
396 False
397 True
398 False
399 False
400 False
401 True
402 False
403 False
404 False
405 False
406 False
407 False
408 False
409 True
410 False
411 False
412 False
413 False
414 False
415 False
416 False
417 False
418 False
419 True
420 False
421 True
422 False
423 False
424 False
425 False
426 False
427 False
428 False
429 False
430 False
431 True
432 False
433 True
434 False
435 False
436 False
437 False
438 False
439 True
440 False
441 False
442 False
443 True
444 False
445 False
446 False
447 False
448 False
449 True
450 False
451 False
452 False
453 False
454 False
455 False
456 False
457 True
458 False
459 False
460 False
461 True
462 False
463 True
464 False
465 False
466 False
467 True
468 False
469 False
470 False
471 False
472 False
473 False
474 False
475 False
476 False
477 False
478 False
479 True
480 False
481 False
482 False
483 False
484 False
485 False
486 False
487 True
488 False
489 False
490 False
491 True
492 False
493 False
494 False
495 False
496 False
497 False
498 False
499 True
500 False
501 False
502 False
503 True
504 False
505 False
506 False
507 False
508 False
509 True
510 False
511 False
512 False
513 False
514 False
515 False
516 False
517 False
518 False
519 False
520 False
521 True
522 False
523 True
524 False
525 False
526 False
527 False
528 False
529 False
530 False
531 False
532 False
533 False
534 False
535 False
536 False
537 False
538 False
539 False
540 False
541 True
542 False
543 False
544 False
545 False
546 False
547 True
548 False
549 False
550 False
551 False
552 False
553 False
554 False
555 False
556 False
557 True
558 False
559 False
560 False
561 False
562 False
563 True
564 False
565 False
566 False
567 False
568 False
569 True
570 False
571 True
572 False
573 False
574 False
575 False
576 False
577 True
578 False
579 False
580 False
581 False
582 False
583 False
584 False
585 False
586 False
587 True
588 False
589 False
590 False
591 False
592 False
593 True
594 False
595 False
596 False
597 False
598 False
599 True
600 False
601 True
602 False
603 False
604 False
605 False
606 False
607 True
608 False
609 False
610 False
611 False
612 False
613 True
614 False
615 False
616 False
617 True
618 False
619 True
620 False
621 False
622 False
623 False
624 False
625 False
626 False
627 False
628 False
629 False
630 False
631 True
632 False
633 False
634 False
635 False
636 False
637 False
638 False
639 False
640 False
641 True
642 False
643 True
644 False
645 False
646 False
647 True
648 False
649 False
650 False
651 False
652 False
653 True
654 False
655 False
656 False
657 False
658 False
659 True
660 False
661 True
662 False
663 False
664 False
665 False
666 False
667 False
668 False
669 False
670 False
671 False
672 False
673 True
674 False
675 False
676 False
677 True
678 False
679 False
680 False
681 False
682 False
683 True
684 False
685 False
686 False
687 False
688 False
689 False
690 False
691 True
692 False
693 False
694 False
695 False
696 False
697 False
698 False
699 False
700 False
701 True
702 False
703 False
704 False
705 False
706 False
707 False
708 False
709 True
710 False
711 False
712 False
713 False
714 False
715 False
716 False
717 False
718 False
719 True
720 False
721 False
722 False
723 False
724 False
725 False
726 False
727 True
728 False
729 False
730 False
731 False
732 False
733 True
734 False
735 False
736 False
737 False
738 False
739 True
740 False
741 False
742 False
743 True
744 False
745 False
746 False
747 False
748 False
749 False
750 False
751 True
752 False
753 False
754 False
755 False
756 False
757 True
758 False
759 False
760 False
761 True
762 False
763 False
764 False
765 False
766 False
767 False
768 False
769 True
770 False
771 False
772 False
773 True
774 False
775 False
776 False
777 False
778 False
779 False
780 False
781 False
782 False
783 False
784 False
785 False
786 False
787 True
788 False
789 False
790 False
791 False
792 False
793 False
794 False
795 False
796 False
797 True
798 False
799 False
800 False
801 False
802 False
803 False
804 False
805 False
806 False
807 False
808 False
809 True
810 False
811 True
812 False
813 False
814 False
815 False
816 False
817 False
818 False
819 False
820 False
821 True
822 False
823 True
824 False
825 False
826 False
827 True
828 False
829 True
830 False
831 False
832 False
833 False
834 False
835 False
836 False
837 False
838 False
839 True
840 False
841 False
842 False
843 False
844 False
845 False
846 False
847 False
848 False
849 False
850 False
851 False
852 False
853 True
854 False
855 False
856 False
857 True
858 False
859 True
860 False
861 False
862 False
863 True
864 False
865 False
866 False
867 False
868 False
869 False
870 False
871 False
872 False
873 False
874 False
875 False
876 False
877 True
878 False
879 False
880 False
881 True
882 False
883 True
884 False
885 False
886 False
887 True
888 False
889 False
890 False
891 False
892 False
893 False
894 False
895 False
896 False
897 False
898 False
899 False
900 False
901 False
902 False
903 False
904 False
905 False
906 False
907 True
908 False
909 False
910 False
911 True
912 False
913 False
914 False
915 False
916 False
917 False
918 False
919 True
920 False
921 False
922 False
923 False
924 False
925 False
926 False
927 False
928 False
929 True
930 False
931 False
932 False
933 False
934 False
935 False
936 False
937 True
938 False
939 False
940 False
941 True
942 False
943 False
944 False
945 False
946 False
947 True
948 False
949 False
950 False
951 False
952 False
953 True
954 False
955 False
956 False
957 False
958 False
959 False
960 False
961 False
962 False
963 False
964 False
965 False
966 False
967 True
968 False
969 False
970 False
971 True
972 False
973 False
974 False
975 False
976 False
977 True
978 False
979 False
980 False
981 False
982 False
983 True
984 False
985 False
986 False
987 False
988 False
989 False
990 False
991 True
992 False
993 False
994 False
995 False
996 False
997 True
998 False
999 False
1000 False
1001 False
1002 False
1003 False
1004 False
1005 False
1006 False
1007 False
1008 False
1009 True
1010 False
1011 False
1012 False
1013 True
1014 False
1015 False
1016 False
1017 False
1018 False
1019 True
1020 False
1021 True
1022 False
1023 False
1024 False
1025 False
1026 False
1027 False
1028 False
1029 False
1030 False
1031 True
1032 False
1033 True
1034 False
1035 False
1036 False
1037 False
1038 False
1039 True
1040 False
1041 False
1042 False
1043 False
1044 False
1045 False
1046 False
1047 False
1048 False
1049 True
1050 False
1051 True
1052 False
1053 False
1054 False
1055 False
1056 False
1057 False
1058 False
1059 False
1060 False
1061 True
1062 False
1063 True
1064 False
1065 False
1066 False
1067 False
1068 False
1069 True
1070 False
1071 False
1072 False
1073 False
1074 False
1075 False
1076 False
1077 False
1078 False
1079 False
1080 False
1081 False
1082 False
1083 False
1084 False
1085 False
1086 False
1087 True
1088 False
1089 False
1090 False
1091 True
1092 False
1093 True
1094 False
1095 False
1096 False
1097 True
1098 False
1099 False
1100 False
1101 False
1102 False
1103 True
1104 False
1105 False
1106 False
1107 False
1108 False
1109 True
1110 False