204. Count Primes

LeetCode medium original: C# #csharp #leetcode #math #medium
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
LeetCode Static

given số nguyên n, return количество простых чисел, которые строго меньше n.

Ví dụ:

Input: n = 10

Output: 4

Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

C# lời giải

đã khớp/gốc 
public class Solution {
    public int CountPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        bool[] numbers = new bool[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = true;
        }
        for (int p = 2; p <= Math.Sqrt(n); ++p) {
            if (numbers[p]) {
                for (int j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }
        int numberOfPrimes = 0;
        for (int i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }
        return numberOfPrimes;
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        bool[] numbers = new bool[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = true;
        }
        for (int p = 2; p <= Math.Sqrt(n); ++p) {
            if (numbers[p]) {
                for (int j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }
        int numberOfPrimes = 0;
        for (int i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }
        return numberOfPrimes;
    }
}

Java lời giải

đã khớp/gốc 
class Solution {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        boolean[] numbers = new boolean[n];
        for (int p = 2; p <= (int) Math.sqrt(n); ++p) {
            if (numbers[p] == false) {
                for (int j = p * p; j < n; j += p) {
                    numbers[j] = true;
                }
            }
        }

        int numberOfPrimes = 0;
        for (int i = 2; i < n; i++) {
            if (numbers[i] == false) {
                ++numberOfPrimes;
            }
        }

        return numberOfPrimes;
    }
}

JavaScript lời giải

đã khớp/gốc 
class Solution {
    countPrimes(n) {
        if (n <= 2) {
            return 0;
        }

        let numbers = new Array(n).fill(true);
        for (let p = 2; p <= Math.sqrt(n); ++p) {
            if (numbers[p]) {
                for (let j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }

        let numberOfPrimes = 0;
        for (let i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }

        return numberOfPrimes;
    }
}

Python lời giải

đã khớp/gốc 
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        numbers = [False, False] + [True] * (n - 2)
        for p in range(2, int(sqrt(n)) + 1):
            if numbers[p]:
                for multiple in range(p * p, n, p):
                    numbers[multiple] = False
        return sum(numbers)

Go lời giải

đã khớp/gốc 
package main

import (
    "math"
)

func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    numbers := make([]bool, n)
    for i := range numbers {
        numbers[i] = true
    }

    for p := 2; p <= int(math.Sqrt(float64(n))); p++ {
        if numbers[p] {
            for j := p * p; j < n; j += p {
                numbers[j] = false
            }
        }
    }

    numberOfPrimes := 0
    for i := 2; i < n; i++ {
        if numbers[i] {
            numberOfPrimes++
        }
    }

    return numberOfPrimes
}

func main() {
    n := 10
    result := countPrimes(n)
    println(result) 
}

Algorithm

1️⃣

Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу.

2️⃣

Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само number p должно быть простым). find наименьшее number в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2.

3️⃣

Когда Thuật toán завершится, все оставшиеся числа, которые не отмечены, являются простыми.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm
Chưa có việc làm đang hoạt động.