從網路課程 程式必修課！離散數學與演算法 來淺嚐一下沒機會在課堂上所學的離散數學與演算法。或許對撰寫程式的效能提昇會有些幫助。
課程相關資訊
[連結]：https://hiskio.com/courses/1196/lectures/133749
本篇範圍：Chapter 5
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
算數基本定理 The Fundamental Theorem of Arithmetic
對於所有大於 1 的整數，可以被展開成一串質數的乘積 (質因數分解) ，而且這也是唯一一組表示方式
質數檢查
1. 檢查該數以下的所有質數是否可整除 (初步)
2. 檢查該數的開平分根以下的所有質數是否可整除 (優化)
該數為兩數的乘積，意味者當兩數相同時，那其值就是剛好為該數的開平分根。以此延伸，若兩數不相同時，一數若小於該數的開平分根，另一數必大於該數的開平分根
程式碼
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
const isPrime = (n) => { if(!Number.isInteger(n) || n<=1) return 'Not Valid Input' let start = 2 let result = true while(start <= n ** 0.5){ if (n % start === 0){ result = false break } start++ } return result } console.log('sss', isPrime('sss')) // Not valid Input console.log('-1.5', isPrime(-1.5)) // Not valid Input console.log('-1', isPrime(-1)) // Not valid Input console.log('0', isPrime(0)) // Not valid Input console.log('1', isPrime(1)) // Not valid Input console.log('1.5', isPrime(1.5)) // Not valid Input console.log('2', isPrime(2)) // true console.log('3', isPrime(3)) // true console.log('10', isPrime(10)) // false const nthPrime = (n) => { if(!Number.isInteger(n) || n<=0) return 'Not Valid Input' const primes = [2,3,5,7,11,13] let start = 17 while(primes.length < n){ let primeChecked = true for(let i=0; i<primes.length; i++){ if(primes[i] > start ** 0.5) break if(start % primes[i] === 0){ primeChecked = false break } } if(primeChecked){ primes.push(start) } start += 2 } return primes[n-1] } console.log(nthPrime('sss')) // Not valid Input console.log(nthPrime(-1.5)) // Not valid Input console.log(nthPrime(-1)) // Not valid Input console.log(nthPrime(0)) // Not valid Input console.log(nthPrime(1)) // 2 console.log(nthPrime(2)) // 3 console.log(nthPrime(10)) // 29 console.log(nthPrime(100)) // 541 |
