#6
by かずま » 5年前
nana0627 さんが書きました: ↑5年前
文字が多くて見づらくてごめんなさい。
インデントを スペース 2個、4個、6個、タブ 1個で書いていますね。
この掲示板で codeタグを使うと、タブはスペース 4個に
置き換えられて見にくくなります。
変数の n と a が問題文と逆なのも分かりにくい原因のひとつです。
また、サブ関数を使わず、main に全部入れていることも問題です。
nana0627 さんが書きました: ↑5年前
ヒントを見て頑張ってみましたが、aが全て1になってしまいました。
a
φ(n) の計算は、φ(n) が求まった後でないとできません。
そのプログラムは、φ(n) を求める途中の値 countを使って
a
count を計算しているのでダメです。
さて最低限の修正は、
コード:
#include <stdio.h>
#define NUMBER 50
int main (void){
int a,b,c,d,e,f,g,h,i,count;
int n[NUMBER];
for (a = 2; a <= NUMBER; a++){
count = 0;
f = 0;
for (b = 1; b < a; b++){
c = a;
d = b;
while (c % d != 0){
e = c % d;
c = d;
d = e;
}
if (d == 1){
count++;
f++;
n[f] = b;
}
} // ★追加
{ // ★追加
i = count;
for (g = 1; g <= i; g++){
h = 1;
count = i; // ★追加
while (count > 0){
h = h * n[g] % a;
count--;
}
if (h == 1)
printf("n = %d, a = %d: verified\n",a,n[g]);
else
printf("***n = %d, a = %d: counterexample found!\n",a,n[g]);
}
}
}
return (0);
}
サブ関数を使えば、
コード:
#include <stdio.h>
#define NUM 50
int gcd(int a, int b)
{
int r;
while (r = a % b) a = b, b = r;
return b;
}
int phi(int n, int *a)
{
int k = 0;
for (int i = 1; i < n; i++)
if (gcd(n, i) == 1) a[k++] = i;
return k;
}
int pow_mod(int a, int k, int n) // pow(a, k) % n
{
int p = 1;
while (k-- > 0) p = p * a % n;
return p;
}
int main(void)
{
for (int a[NUM], n = 2; n <= NUM; n++)
for (int k = phi(n, a), i = 0; i < k; i++)
printf(pow_mod(a[i], k, n) == 1 ? "n = %d, a = %d: verified\n"
: "***n = %d, a = %d: counterexample found!***\n", n, a[i]);
}
[quote=nana0627 post_id=150909 time=1528740455]
文字が多くて見づらくてごめんなさい。[/quote]
インデントを スペース 2個、4個、6個、タブ 1個で書いていますね。
この掲示板で codeタグを使うと、タブはスペース 4個に
置き換えられて見にくくなります。
変数の n と a が問題文と逆なのも分かりにくい原因のひとつです。
また、サブ関数を使わず、main に全部入れていることも問題です。
[quote=nana0627 post_id=150909 time=1528740455]
ヒントを見て頑張ってみましたが、aが全て1になってしまいました。
[/quote]
a[sup]φ(n)[/sup] の計算は、φ(n) が求まった後でないとできません。
そのプログラムは、φ(n) を求める途中の値 countを使って
a[sup]count[/sup] を計算しているのでダメです。
さて最低限の修正は、
[code]
#include <stdio.h>
#define NUMBER 50
int main (void){
int a,b,c,d,e,f,g,h,i,count;
int n[NUMBER];
for (a = 2; a <= NUMBER; a++){
count = 0;
f = 0;
for (b = 1; b < a; b++){
c = a;
d = b;
while (c % d != 0){
e = c % d;
c = d;
d = e;
}
if (d == 1){
count++;
f++;
n[f] = b;
}
} // ★追加
{ // ★追加
i = count;
for (g = 1; g <= i; g++){
h = 1;
count = i; // ★追加
while (count > 0){
h = h * n[g] % a;
count--;
}
if (h == 1)
printf("n = %d, a = %d: verified\n",a,n[g]);
else
printf("***n = %d, a = %d: counterexample found!\n",a,n[g]);
}
}
}
return (0);
}
[/code]
サブ関数を使えば、
[code]
#include <stdio.h>
#define NUM 50
int gcd(int a, int b)
{
int r;
while (r = a % b) a = b, b = r;
return b;
}
int phi(int n, int *a)
{
int k = 0;
for (int i = 1; i < n; i++)
if (gcd(n, i) == 1) a[k++] = i;
return k;
}
int pow_mod(int a, int k, int n) // pow(a, k) % n
{
int p = 1;
while (k-- > 0) p = p * a % n;
return p;
}
int main(void)
{
for (int a[NUM], n = 2; n <= NUM; n++)
for (int k = phi(n, a), i = 0; i < k; i++)
printf(pow_mod(a[i], k, n) == 1 ? "n = %d, a = %d: verified\n"
: "***n = %d, a = %d: counterexample found!***\n", n, a[i]);
}
[/code]