LeetCode204題（一刷）

LeetCode204題

解法一

歐拉算法

class Solution { public int countPrimes(int n) {

byte[] check = new byte[n];//用來标記是否已經通路過了，如果通路過了就打1，沒通路過打0
int[] primeList = new int[n]; //用來記素數


int count = 0;//用來記錄素數個數
for(int i = 2;i< n;i++) {
    if(check[i]==0) {    //打了1的就不會再看了，重複指派浪費時間
        primeList[count++] = i; //count變量記錄素數個數，數組記錄已知的素數的值
    }
    
    for(int j=0;j<count&&i*primeList[j]<n;j++) {
        if(i*primeList[j]>n) {       
            break;
        }
        
        check[i*primeList[j]] = 1; //标記 x=i*primeList[j],x位置是我通路過的位置，打1
        if(i%primeList[j]==0) {   //這一部分不好了解，比方說6，之前通路過（2,3），那麼6%2==0,不用再檢查6%3了，真正負責記錄資料的是count變量
            break;
        }
        
    }
    
    
}

return count;
           

連結：https://leetcode-cn.com/problems/two-sum/solution/shi-yong-ou-la-suan-fa-by-deep-dark/

解法二

厄拉多塞篩法

class Solution {

public int countPrimes(int n) {

int[] nums = new int[n];
  
    
    for(int i=2;i<n;i++) {
        nums[i] = 1;
    }
   
    int res = 0;
    int t = (int)Math.sqrt(n);
    for(int i=2;i<=t;i++) {
        if(nums[i]==1) {
           
            for(int j=2; j*i<n;j++) {
                nums[j*i] = 0;
                
            }
        }
    }
    
    for(int i:nums) {
        res+=i;
    }
    
    return res;
    
    
    
    
    
    
    
    
}
           

}