牛牛想知道[7,n)内有多少素数,只不过他不知道怎么做,所以他想请你帮忙。
给定一个数字n,返回[7,n)内有多少素数。
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
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; } };
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; }