P1174 互素
2024-09-21 01:41:05
P1174 互素
时间: 1000ms / 空间: 131072KiB / Java类名: Main
描述
对于某个数n,,我们这次的工作仅是求出小于n且和n互质的数的个数,,比如n=10时 1,3,7,9均与10互质
//互质的定义是gcd(a,b)=1
输入格式
输入只有一行,一个数N(1<=N<=2,000,000,000)。
输出格式
输出也只有一行,输出和小于n且和n互质的数的个数
测试样例1
输入
10
输出
4
----------------------------------------------------------------------------------------
* 欧拉函数是指:对于一个正整数n,小于n且和n互质的正整数(包括1)的个数,记作φ(n) 。
通式:φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数,x是不为0的整数。φ(1)=1(唯一和1互质的数就是1本身)。
-------------------------------------------------------------------------------------------------------------------
评测状态 Accepted
题目 P1174 互素
提交时间 2016-03-27 09:21:23
代码语言 Java
消耗时间 1325 ms
消耗内存 14288 KiB
----------------------------------------------------------------
import java.util.Scanner;
public class Main { public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int i;
int cnt=n;
for(i=2;n!=1;i++){
if(n%i==0){
cnt-=cnt/i;
while(n%i==0) n/=i;
}
}
System.out.println(cnt);
}
sc.close(); } }
最新文章
- JS这些代码你都不会,你还有什么好说的!!!
- SQLite 创建自增长标识列
- paip.编程语言方法重载实现的原理及python,php,js中实现方法重载
- 用CSS box-shadow画画
- mac os x常用快捷键及用法
- js实现加减乘除
- Hibernate学习笔记--环境搭建及运行
- 那些年,我们一起学WCF--(6)PerCall实例行为
- Entity Framewor 学习笔记 (include + where)
- IE9的window.showmodaldialog显示问题
- 【ecos学习1】wmware运行redboot[方法一]--脚本实现配置
- 三星galaxy S4快捷功能
- Linux下tomcat管理查看控制台|杀死tomcat进程
- 打字机效果-so easy
- python_黑洞数
- CF920E Connected Components?
- java.lang.NoClassDefFoundError: org/apache/hadoop/hbase/HBaseConfiguration] with root cause
- 【PyQt5-Qt Designer】窗口操作
- yarn 学习 小记
- Java Switch支持的类型问题