问题描述

在计算机科学中，最长递增子序列(longest increasing subsequence,简称LIS)问题是指在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能大。注意：最长递增子序列中的元素在原序列中不一定是连续的。 解决最长递增子序列问题的算法最低要求O(nlogn)。

基本原理

素数，又叫质数，除了1和它本身以外不再有其他的因数。

代码模板

1
2
3
4
5
6
7
8
9
10

1） 时间复杂度是O(n)
---------------------

bool prime(int x){//判断x是不是质数，是返回true，不是返回false
    if(x <= 1) return false;
    for(int i = 2; i < x; i ++){
        if(x % i == 0) return false;
    }
    return true;
}