c语言欧拉函数素数,C语言函数素数

关于欧拉函数 如果 p 是素数，则φ( p) = p-1φ( p) = p-1 对吗？？

根据欧拉函数的通式φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),如果x是素数，那么

φ(x)=x(1-1/x)=x-1

所以是对的

相关问答

Q1: c语言输出100到200之间的素数

解题思路：

首先先找出来100~200以内的所有整数，再让这些整数对除了1和它本身以外的数求余，如果有能整除的就不是素数，否则就为素数。

先找出来100到200的所有整数,都为i

用i去对除了1和它本身以外的数求余。

正确的代码：

#includestdio.h

int main()

{

int conut = 0;

int i = 0;

for(i=100; i=200; i++) 

{

int j = 0;

for(j=2; ji; j++)

{

if(i%j == 0)

break;

}

if(j==i)

{

conut++;

printf("%d ", i);

}

}

printf("\n");

printf("素数个数为：%d\n", conut);

return 0;

}

第二个if语句的判断条件应该是j==i；而不是i%j 。

扩展资料：

实现的其他方法：

需要用到sort函数，也就是开平方根函数。头文件为#includemath.h。 显而易见，任何一个数，每一对因子都是由这个数开平方后的数的左右各一个组成，所以，在求余过程中，只需要对从2到开平方之后的数求余即可。遇到可以整除的就不是素数，否则就为素数。

代码：

#includestdio.h

#includemath.h

int main()

{

int count = 0;

int i = 0;

for(i=100; i=200; i++)

{

int j = 0;

for(j=2; j=sqrt(i); j++)

{

if(i%j == 0)

break;

}

if(j sqrt(i))

{

count++;

printf("%d ",i);

}

}

printf("\n");

printf("素数个数为：%d", count);

return 0;

}

Q2: c++描述欧拉筛法求m到n的素数

按照你的要求编写的用欧拉筛选法求从M到N的素数的C++程序如下

#includeiostream

#includecstring

using namespace std;

int main(){

int M,N,cnt=0,count=1,prime[100001];

bool vis[100001];

memset(vis,false,sizeof(vis));

memset(prime,0,sizeof(prime));

cinMN;

for(int i=2;i=N;i++){

if(!vis[i]){

prime[cnt++]=i;

if(i=M){

if(count++%5==0){

coutiendl;

}else{

couti" ";

}

}

}

for(int j=0;jcnt i*prime[j]=N;j++){

vis[i*prime[j]]=true;

if(i%prime[j]==0) break;

}

}

return 0;

}

Q3: C语言实现欧拉函数

int eular(int n)

{

int ret=1,i; //定义变量

for(i=2;i*i=n;i++) //从i=2开始循环，判定条件为i*i小于等于n，循环一次i增加1

if(n%i==0) //判定条件为n除以i的余数等于0

{

n/=i,ret*=i-1; //n=n/i，ret = ret*(i-1)

while(n%i==0) //当n除以i的余数等于0时执行下面的语句，否则跳过

n/=i,ret*=i;

}

if(n1) //如果n1执行下面语句，否则跳过

ret*=n-1; //ret = ret*(n-1)

return ret;

}

直接复制的百度百科的，没具体看是什么功能

Q4: 写一个函数int prime(int x)，判断数值x是否素数，如果是返回1，否则返回0。

源代码如下：

#include stdio.h

#include math.h

int prime(int x)

{ int i;

for(i=2;ix;i++)

if(x%i==0)

return 0;

else return 1; }

main()

{

int x,m;

printf("请输入需要判断的数字：\n");

scanf("%d",x);

m=prime(x);

if(m==1)

{  printf("%d是素数\n",x); }

else

{  printf("%d不是素数\n",x); } }

扩展资料：

素数性质

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，

是素数或者不是素数。

如果

为素数，则

要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。

1、如果 为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。

2、其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，哈里·弗斯滕伯格则用拓扑学加以证明。

参考资料来源：百度百科-C语言

百度百科-质数

Q5: C语言输出100-200之间的素数

逻辑错误，准确位置为14行，正确代码如下：

#includestdio.h

int main()

{

int i = 0;

for (i=100; i=200; i++)

{

int j = 0;

for (j=2; j=i-1; j++)

{

if (i%j == 0)

{

break;

}

}

if (j=i)

{

printf("%d",i);

}

}

return 0;

}

扩展资料：

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，

是素数或者不是素数。

如果

为素数，则

要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。

如果 为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。

其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，哈里·弗斯滕伯格则用拓扑学加以证明。