牛牛与素数(2)

[编程题]牛牛与素数(2)

热度指数：705 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛想知道[7,n)内有多少素数，只不过他不知道怎么做，所以他想请你帮忙。

给定一个数字n，返回[7,n)内有多少素数。

示例1

输入

输出

备注:

算法知识视频讲解

下一个影子

竟然不能包含n本身！！！

发表于 2021-10-20 20:20:19 回复(0)

Python 3

ZhongHaoWang

素数筛

class Solution:
    def solve(self , n ):
        # write code here
        # 素数筛
        prime = []
        visited = [False] * (n)
        ans = 0
        for i in range(2,n):
            if not visited[i]:
               ans += 1
               prime.append(i)
         
            j = 0
            while j < len(prime) and i * prime[j] <= n - 1:
                 visited[prime[j] * i] = 1
                 if i % prime[j] == 0:
                    break
                 j += 1
        return ans - 3

发表于 2021-08-28 10:39:03 回复(0)

Python

spongebob7

import math
class Solution:
def solve(self , n ):
is_prime = [1]*1000001
is_prime_with = [2,3]
for i in range(4,1001):
for j in range(2,int(math.sqrt(i))+1):
if i%j==0:
is_prime[i]=0
if is_prime[i]==1:
is_prime_with.append(i)
ans = 0
for i in range(7,n):
if i>1000:
ans += self.judge(i, is_prime_with)
else:
ans+=is_prime[i]
return ans
def judge(self,i,arr):
for a in arr:
if i%a==0:
return 0
return 1

发表于 2021-03-26 16:09:25 回复(0)

---459---

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个数字n，返回[7,n)内有多少素数。
     * @param n int整型 代表题目中的n
     * @return int整型
     */
    int solve(int n) {
        // write code here
        int count = 0;
        bool flag;
        for(int i = 7; i < n; i++){
            flag = true;
            for(int j = 2; j <= sqrt(i); j++){
                if(i % j == 0){
                    flag = false;
                    break;
                }
            }
            if(flag){
                count ++;
            }
        }
        return count;
    }
};

发表于 2021-03-07 14:26:04 回复(0)

牛客37697243号

我的方法有那么不堪吗？

    public int solve(int n) {
        // write code here
        if (n < 8) return -1;
        List<Integer> list = new ArrayList(){{
            this.add(2);
            this.add(3);
            this.add(5);
            this.add(7);
        }};

        for (int i = 8; i < n; i++) {
            boolean isPrime = true;
            for (Integer num : list) {
                if (i % num == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) list.add(i);
        }

        return list.size() - 3;
    }

发表于 2021-02-22 14:59:16 回复(0)