Database(5) -- Data Type and DDL

LeetCode Day 33: P204. Count Primes (Easy)

题目：

给一个非负整数n，求小于n的所有质数的个数。

思路：

常规思路会非常慢，小于n的数，每个数都需要检查它是不是素数，而检查的办法，就是看它的约数的个数，如果大于2，则不是素数。 这样时间复杂度就会是n^2

答案：

public class E_204_CountPrimes {
    public int countPrimes(int n) {
        if (n < 3)
            return 0;

        boolean[] f = new boolean[n];
        //Arrays.fill(f, true); boolean[] are initialed as false by default
        int count = n / 2;
        for (int i = 3; i * i < n; i += 2) {
            if (f[i])
                continue;

            for (int j = i * i; j < n; j += 2 * i) {
                if (!f[j]) {
                    --count;
                    f[j] = true;
                }
            }
        }
        return count;
    }
}

看了很长时间，甚至一步一步debug, 也没明白到底为什么这么做。重新看答案，原来用了一个方法叫Sieve of Eratosthenes。

埃拉托斯特尼筛法：

比如，求小于210的质数，就把从2开始，所有的数都列出来，然后挨个看：第一个数是2，于是就把210以内所有2的倍数都筛掉； 然后是3，于是就把210以内所有3的倍数都筛掉；然后剩下的是5，所有把210以内所有5的倍数都筛掉……

筛到17时，因为17的平方已经大于210，所以就不用再筛了。剩下的所有的数就是210以内的素数。

https://www.youtube.com/watch?v=GxoMWxXLKMc

public class E_204_CountPrimes {
    public int countPrimes(int n) {
		//默认值是false,如果是不是素数我们标为true
		//当然你也可以使用 Arrays.fill(f, true);  默认全设为true，如果不是素数我们设为false
		boolean s[] = new boolean[n];
		
		//如果n小于3的话就没有  因为找到n以内  所以2以内是没有的
		if(n < 3)return 0;
		
		//c 可以理解为最多的素数个数
		//以为我们知道所有的偶数都不是素数，所有我们可以剔除一半
		//但是你可能会有疑问 2 不是偶数吗   --> 这里 2 和 1 相抵消
		//比如 5 以内的话  5 / 2 = 2 素数就为 2 和 3
		//首先我们假设 小于 c 的奇数全是素数
		int c = n / 2;

		// 之后我们只要剔除 在这个奇数范围内 不是素数的数就可以了
		// 因为我们已经把偶数去掉了，所以只要剔除奇数的奇数倍就可以了
		for(int i = 3; i * i < n; i += 2) {
			//说明 i 是不是素数，而且已经是剔除过的
			if(s[i])
				continue;
			
			//这里是计算c 中剔除完不是素数的奇数个数  下面解释各个值的含义
			//我们要剔除的是 i 的 奇数倍
			//为什么是 i * i开始呢   我们打个比方，假设我们此时i = 5
			//那么我们开始剔除  j = 1 时就是本身，此时要么已经被剔除，要么就是素数，所以 1 不考虑
			//当 j = 2 || j = 4时，乘积为偶数所以也不在我们考虑范围内
			//当 j = 3时，我们考虑 3 * 5 但是这种情况已经是当 i = 3的时候被考虑进去了所以我们只要考虑之后的就可以了
			
			//那么为什么 j = j + i * 2呢
			//根据上面所说 我们从3开始考虑 3 * 3,3 * 5,3 * 7....只要 j < n 我们就剔除
			//带入i : i * i, i * ( i + 2 ) , i * ( i + 4 )....
			for(int j = i * i; j < n; j+= i * 2) {
				//只要找到c个奇数中的合数，c就减1，把 j标记为非素数
				if(!s[j]) {
					s[j] = true;
					c --;
				}
			}
		}
		return c;
	}
}

Database:

Data Types

Character Strings

• CHAR(n) denotes a fixed-length string of up to n characters. Important: Short strings are padded to make n characters with trailing blanks.
• VARCHAR(n) denotes a string of up to n characters.

Bit Strings

• BIT(n)
• BIT VARYING(n)

Boolean

TRUE, FALSE, UNKNOWN

Integer

INT or INTEGER, SHORTINT

Floating-point numbers

FLOAT, REAL, DOUBLE

DECIMAL(n, d) allows values that consist of n decimal digits, with the decimal point assumed to be d positions from the right. NUMERIC is similar.

Dates and times

Dates and Times

DATE ‘1984-05-14’

TIME ‘15:00:02.5’

Create a table

CREATE TABLE Movies(
    title       CHAR(100),
    year        INT,
    length      INT,
    genre       CHAR(10),
    studioName  CHAR(30),
    producerC#  INT
);

Delete a table

DROP TABLE R;

Modify a table

ALTER TABLE t ADD phone CHAR(16);
ALTER TABLE t DROP birthdate;

Default Values

gender CHAR(1) DEFAULT '?',
birthdate DATE DEFAULT DATE '0000-00-00'

Declaring Keys

Two ways:

a) PRIMARY KEY: null is not allowed B) UNIQUE: null is allowed

CREATE TABLE  MovieStar (
    name CHAR(30) PRIMARY KEY ,
    address VARCHAR(255),
    gender CHAR(1),
    birthdate DATE
);

AES Encrypt and Decrypt

SELECT HEX(AES_ENCRYPT("HelloWorld","new retail"));

SELECT AES_DECRYPT(UNHEX("799531CA0BEB4078163F10BD4D081DDC"),"new retail");