著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。
示例 1：
输入：n = 2 输出：["1/2"] 解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
示例 2：
输入：n = 3 输出：["1/2","1/3","2/3"]
示例 3：
输入：n = 4 输出：["1/2","1/3","1/4","2/3","3/4"] 解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
示例 4：
输入：n = 1 输出：[]
提示：
1 <= n <= 100GCD辗转相除法【欧几里德算法（Euclidean algorithm）】
相关知识链接碾转相除法
这是一个求最大公约数的方法
gcd(int a, int b)辗转相除方法，判断两个数的最大公约数是否为1i到n和从i+1到n的分子分母关系了class Solution {
public List<String> simplifiedFractions(int n) {
List<String> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <=n ; j++) {
if (gcd(i,j)==1){
list.add(i+"/"+j);
}
}
}
return list;
}
int gcd(int a, int b){
if (b==0){
return a;
}
return gcd(b,a%b);
}
}统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
0 <= n <= 5 * 106题解，求小于n的质数，一上来一看好像挺简单，还简单题。
挨个算嘛，暴力求解
class Solution {
public int countPrimes(int n) {
if (n<2){
return 0;
}
if (n==2){
return 0;
}
List<Integer> list = new ArrayList<>();
list.add(2);
boolean isPrimes = true;
for (int i = 3; i < n ; i++) {
isPrimes = true;
for(int num : list){
if (i % num == 0){
isPrimes = false;
break;
}
}
if (isPrimes){
list.add(i);
}
}
return list.size();
}
}结果直接超时，心想不至于吧。。还能超时。然后找了张纸画了个矩阵图看了看。
如下
于是萌生了一个想法，我只要把小于n的数去掉了这些能用乘积法求出来的数，剩下的数字不就是质数了么。这过程中还有一个细节点，比如2×6=12,3×4=12，这俩是重复的，需要判断处理下。于是得到了代码如下：
class Solution {
public int countPrimes(int n) {
if (n<=2){
return 0;
}
int count = 0;
int tmp = 0;
int[] res = new int[n];
for (int i = 2; i*i < n; i++) {
for (int j = i; j*i < n; j++) {
tmp = i*j;
if (res[tmp] == 0){
res[tmp] = 1;
count++;
}
}
}
return n - count - 2;
}
}最终结果需要额外减去2是因为前面1、2的结果都为0，需要额外减去。
解答成功:
执行耗时:139 ms,击败了8.31% 的Java用户
内存消耗:56.4 MB,击败了17.00% 的Java用户结果好像不太理想，还能再优化？
class Solution {
public int countPrimes(int n) {
if (n == 0 || n == 1) return 0;
int[] arr = new int[n];
arr[0] = 1;
arr[1] = 1;
int count = 0;
for (int i = 2; i * i < n; i++) {
if (arr[i] == 1) continue;
for (int j = 2 * i; j < n; j += i) {
if (arr[j] == 0){
arr[j] = 1;
count++;
}
}
}
return n - count - 2;
}
}