首页 > 数据结构 > Hash表 > POJ 2407 Relatives [解题报告] Java
2013
11-11

POJ 2407 Relatives [解题报告] Java

Relatives

问题描述 :

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

输入:

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

输出:

For each test case there should be single line of output answering the question posed above.

样例输入:

7
12
0

样例输出:

6
4

解题代码:


方法一:
import java.util.Scanner; import java.util.Arrays; public class Main { // 求从1到n-1与n互质的数的个数,代码如下 static int eular(int n) { int ret = 1,i; for (i = 2;i * i <= n;i++) if (n % i == 0) { n /= i; ret *= (i - 1); while (n % i == 0) { n /= i; ret *= i; } } if (n > 1) ret *= (n - 1); return ret; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); if(n==0) break; System.out.println(eular(n)); } } } 方法二: //* @author [email protected] import java.util.HashSet; import java.util.Scanner; import java.util.Vector; public class Main { public static Vector< Double> fact(double n){ HashSet< Double> set=new HashSet< Double>(); while(n%2==0){ n/=2; set.add(2.0); } double k=3; while(k<=(Math.sqrt(n+0.0)+1)){ if(n%k==0){ n/=k; set.add(k); } else k+=2; } if(n>1)set.add(n); return new Vector< Double>(set); } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=0; double val=0; Vector< Double> set; while((n=scan.nextInt())!=0){ val=n; set=fact(n); for(int i=0;i< set.size();i++){ val*=1.0-1.0/set.get(i); } System.out.println((int)val); } } }

  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环