牛客网OR86返回小于N的质数个数(动态规划)

题目描述

请考虑性能

输入描述:

一个整数N

输出描述:

小于N的质数数量

 

思路：

这题目需要用到动态规划，比如输入的值是10，小于10的质数个数=小于9的质数个数加上0（因为10不是质数所以+0，如果当前的是质数就+1） 以此类推，小于9的质数个数=小于8的质数个数+1或0（根据改数字是不是质数来选择）

结论：

小于当前的数的质素个数=小于前一个数的质数个数+（1或0）

这样我们每一次只需要判断一个数是不是质数就可以了

 

喜欢的老铁们留个赞再走呗

 

放代码：

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner cin = new Scanner(System.in);

		int n = cin.nextInt();

		int a[] = new int[n - 1];// 定义一个一维数组并申请空间（因为质数是从2开始的所以我们只需要考虑n-1个数就可以了）

		a[0] = 1;// 数组2

		for (int i = 3; i <= n; i++) {
			int temp = 1;// 判断当前的数是不是质数的暂时变量

			// 判断当前的数是不是质数，
			for (int j = 2; j < i; j++) {

				if (i % j == 0) {// 被整除了说明不是质数

					temp = 0;// 把暂时变量的值更新为0表示不是质数
					break;// 结束循环
				}

			}
			// a[i-2],因为数字是从3开始的，3是数组中的第二个元素，所以需要i-2;
			a[i - 2] = a[i - 3] + temp;// 小于当前数的质数数量是在这个数前面 的质数数量加上暂时变量

		}

		System.out.println(a[n - 2]);// 输出结果（n-2）表示的是最后一个元素就是第n个元素

	}

}