C言語でペナン数を求めて素数を調べる

暇じゃないけどペナン数列を求めてみた

もう就活を初めて、SPIの勉強もしないといけないけど、大学で読んでたニュートンっていう雑誌で”ペナン数を使って素数を求められる”って感じの記事があったのを急に思い出したので、C言語でペナン数を求めて、そっから素数を求めてみた。

ペナン数とは

詳しくはGoogle先生に聞いてください...まぁ

ペラン数（英: Perrin number）とは、以下の漸化式で定義される数である。

また、これによって得られる以下の数列をペラン数列と呼ぶ。

ja.wikipedia.org

でこの数列は、n番目のペラン数がnで割り切れたら，nは素数であるという性質がある。(すべてが成り立つ訳ではないみたい)

C言語でペラン数列を求めてみる！

#include <math.h>
#include <stdio.h>

int main(void)
{
    int x = 130; //出力するペナンの数
    double penan[1000]={3,0,2}; //ペナン数が入る為の配列

    printf("%d番目%.0lf\n",0,penan[0]);
    printf("%d番目%.0lf\n",1,penan[1]);
    printf("%d番目%.0lf\n",2,penan[2]);

    //ペナン数を求める
    for (int t = 3; t < x+1; t++) {
        penan[t] = penan[t-2]+penan[t-3];
        printf("%d番目%.0lf\n",t,penan[t]);
    }

    printf("---<素数判定>---\n");
    for (int i = 1; i < x+1; i++) {
        if(fmod(penan[i],i) == 0){
            printf("%d\n",i);
        }
        else{}
    }
    return 0;
}

結果

0番目3
1番目0
2番目2
3番目3
4番目2
5番目5
6番目5
7番目7
8番目10
9番目12
10番目17
11番目22
12番目29
13番目39
14番目51
15番目68
16番目90
17番目119
18番目158
19番目209
20番目277
21番目367
22番目486
23番目644
24番目853
25番目1130
26番目1497
27番目1983
28番目2627
29番目3480
30番目4610
31番目6107
32番目8090
33番目10717
34番目14197
35番目18807
36番目24914
37番目33004
38番目43721
39番目57918
40番目76725
41番目101639
42番目134643
43番目178364
44番目236282
45番目313007
46番目414646
47番目549289
48番目727653
49番目963935
50番目1276942
51番目1691588
52番目2240877
53番目2968530
54番目3932465
55番目5209407
56番目6900995
57番目9141872
58番目12110402
59番目16042867
60番目21252274
61番目28153269
62番目37295141
63番目49405543
64番目65448410
65番目86700684
66番目114853953
67番目152149094
68番目201554637
69番目267003047
70番目353703731
71番目468557684
72番目620706778
73番目822261415
74番目1089264462
75番目1442968193
76番目1911525877
77番目2532232655
78番目3354494070
79番目4443758532
80番目5886726725
81番目7798252602
82番目10330485257
83番目13684979327
84番目18128737859
85番目24015464584
86番目31813717186
87番目42144202443
88番目55829181770
89番目73957919629
90番目97973384213
91番目129787101399
92番目171931303842
93番目227760485612
94番目301718405241
95番目399691789454
96番目529478890853
97番目701410194695
98番目929170680307
99番目1230889085548
100番目1630580875002
101番目2160059765855
102番目2861469960550
103番目3790640640857
104番目5021529726405
105番目6652110601407
106番目8812170367262
107番目11673640327812
108番目15464280968669
109番目20485810695074
110番目27137921296481
111番目35950091663743
112番目47623731991555
113番目63088012960224
114番目83573823655298
115番目110711744951779
116番目146661836615522
117番目194285568607077
118番目257373581567301
119番目340947405222599
120番目451659150174378
121番目598320986789900
122番目792606555396977
123番目1049980136964278
124番目1390927542186877
125番目1842586692361255
126番目2440907679151155
127番目3233514234548132
128番目4283494371512410
129番目5674421913699287
130番目7517008606060542

- - <素数判定>---

1
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127

コードを詳しく見る

ペナン数を求める

 int x = 130; //出力するペナンの数
    double penan[1000]={3,0,2}; //ペナン数が入る為の配列

    printf("%d番目%.0lf\n",0,penan[0]);
    printf("%d番目%.0lf\n",1,penan[1]);
    printf("%d番目%.0lf\n",2,penan[2]);

    //ペナン数を求める
    for (int t = 3; t < x+1; t++) {
        penan[t] = penan[t-2]+penan[t-3];
        printf("%d番目%.0lf\n",t,penan[t]);
    }

ここがペナン数を求めているところです。
double型で定義されているpenan[1000]の要素数は、テキトーに大きい数を入れときました。そして要素数0~2にペナン数の最初の数の3,0,2を入れて定義してます。その次のfor文で、3番目以降のペナン数を求めて、表示しています。

素数かどうか

printf("---<素数判定>---\n");
    for (int i = 1; i < x+1; i++) {
        if(fmod(penan[i],i) == 0){
            printf("%d\n",i);
        }
        else{}
    }

この部分のfor文で、”i番目のペナン数”を"i"で割って,素数かどうかを判定しています。
このとき、もし余りが0なら素数なので、printfで表示します。0じゃないなら何もしません。
これをi=1からiがx+1番目より大きくなるまで繰り返します。(i=0からじゃないのは、i=0の時は分母が0になり計算できない為)

結果について

結果

- - <素数判定>---

1
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127

出力するペナンの数を130より増やしてみると一応出力はされますが、値がおかしくなっていました。多分double型で表示出来る値を超えたからだと思います。
素数は127まで正確に求める事が出来ました。

多分もっとペナン数を表示させようと思ったら出来ると思います。

みなみのブログ

いろんなことをやろうと思ってる

C言語でペナン数列を求めてみた！あと素数を求めた