4、计数质数、罗马数字转整数、3的幂、Fizz Buzz

计数质数

统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

质数的特点：

1.除了1以外的自然数如果只能被1和它本身整除这个数就是质数
2.合数 能被除1和本身以外的数整除， 这个数一定小于等于合数的开平方

var countPrimes = function(n) {
    let res = 0,isPrime = new Array(n).fill(1) 
    //Array(n).fill(1) 创建一个长度为n的数组并且填充值为1
    for(let i=2;i<n;i++){
        if(isPrime[i]){
            res++
            for(let j=i*2;j<n;j+=i){ //把二倍及以上的倍数筛掉
                isPrime[j] = 0
            }
        }
    }
    console.log(isPrime,res)

};

优化：
上述解法，被重复筛选。例如10，2时筛1次，5时又1次。如何减少重复呢？
举例5。16以内，从2起，5的倍数，5 * 2，5 * 3。
在2和3时倍数时，被筛选过
n以内，从2起，任意数i的倍数，i * 2，i * 3 ... i * i ... i * x(x > i) < n
在i之前的倍数，一定在遍历到i前，被筛选过

var countPrimes = function(n) {
    let res = 0,isPrime = new Array(n).fill(1) 
    //Array(n).fill(1) 创建一个长度为n的数组并且填充值为1
    for(let i=2;i<n;i++){
        if(isPrime[i]){
            res++
            for(let j=i*i;j<n;j+=i){ //把二倍及以上的倍数筛掉
                isPrime[j] = 0
            }
        }
    }
    console.log(isPrime,res)

};

罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3

var romanToInt = function(s) {
    let sMap = new Map()
    sMap.set('I',1)
    sMap.set('V',5)
    sMap.set('X',10)
    sMap.set('L',50)
    sMap.set('C',100)
    sMap.set('D',500)
    sMap.set('M',1000)
    let count = 0
    for(let i=0;i<s.length;i++){
//通常情况下，罗马数字中小的数字在大的数字的右边。
        if(sMap.get(s[i])<sMap.get(s[i+1])){
            count-=sMap.get(s[i])
        }else{
            count+=sMap.get(s[i])
        }
    }
    console.log(count)
};

romanToInt('MCMXCIV') //1994

3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
示例 1：
输入：n = 27
输出：true

var isPowerOfThree = function(n) {
    while(Math.floor(n)==n&&n>0){
        if(n==1){
            return true
        }
        n = n/3
    }
    return false
};

Fizz Buzz

写一个程序，输出从 1 到 n 数字的字符串表示。

1. 如果 n 是3的倍数，输出“Fizz”；

2. 如果 n 是5的倍数，输出“Buzz”；

3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

var fizzBuzz = function(n) {
    let arr = []
    for(var i=1;i<=n;i++){
        if(i%3==0&&i%5==0){
            arr.push('FizzBuzz')
        }else if(i%5==0){
            arr.push('Buzz')
        }else if(i%3==0){
            arr.push('Fizz')
        }else{
            arr.push(i.toString())
        }
    }
    return arr
};