- Problem 1:Multiples of 3 and 5
- Problem 2:Even Fibonacci numbers
- Problem 3:Largest prime factor
- Problem 4:Largest palindrome product
- Problem 5:Smallest multiple
- Problem 6:Sum square difference
- Problem 7:10001st prime
- Problem 8：Largest product in a series
- Problem 9:Special Pythagorean triplet
- Problem 10:Summation of primes
欧拉计划（Project Euler）是一个具有挑战性的不仅仅需要具备数学能力的“数学/计算机编程”问题集合。数学方面的知识可以帮助你获得优雅而高效的解决方案，与此同时，计算机应用和编程技巧也不可或缺。
Y叔：用心学习便能专业，多实战练习很重要，projecteuler和rosalind是你的朋友！
jinglong：个人感觉学习R最重要的还是动手去做，在练习中去学习，去理解，然后再学习相关的理论，自然就能融会贯通。
配合教程：R语言教程/Advanced R/R for Data Science
Problem 1:Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
i =0
sum =0
for(i in 1:999) {
if(i%%5==0|i%%3==0){ # %%整除取余
sum = sum + i
}
}
print(sum)
# 答案：233168
# 易犯错的地方是会把1000也算入
Problem 2:Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
a1 = 1
a2 = 2
i = 0
even_sum = a2
while(i < 4000000){
i = a1 + a2
a1 = a2
a2 = i
if(i%%2==0){
even_sum = even_sum + i
}
}
print(even_sum)
# 答案：4613732
# 解题要先从自己已知答案的小数据集开始找解决方案
Problem 3:Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
num = 600851475143
i = 2
while(T){
i = i + 1
if(num%%i == 0){
num = num/i
j = i
}else if(i>num){
break
}
}
print(j)
# 答案是6857
# 代码只能用来判断奇数，判断偶数存在得到的结果不是质数的问题
Problem 4:Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
t1<-Sys.time()
k = 1
for (i in 100:999) {
for (j in 100:i) {
a = i*j
b = reverse(as.character(a))
if(a==b){
num[k] = a
k = k +1
}
}
}
print(max(num))
t2<-Sys.time()
print(t2-t1)
# 答案：906609
# 就是有点小慢
# 1.363848 mins
Problem 5:Smallest multiple
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Smallest_multiple <- function(range){
prime_judge <- function(num){
mark <-1
for (i in 2:(num-1)) {
if(num%%i==0){
mark <- 0
}
}
return(mark)
}
max_powder <- function(num,max_num){
i <- 0
while (T) {
if(num^i <= max_num) {
index <- num^i
i = i + 1
}else{
break
}
}
return(index)
}
k <- vector()
k[1] <- 2
j <- 2
for (i in 2:(range) ) {
if(prime_judge(i)){
k[j] = i
j <- j + 1
}
}
result <- 1
for (n in k) {
result <- result * max_powder(n,range)
}
print(result)
}
Smallest_multiple(20)
# 答案：232792560
# 尝试用其他的：
# > Smallest_multiple(10)
# [1] 2520
# > Smallest_multiple(20)
# [1] 232792560
# > Smallest_multiple(3)
# [1] 6
# > Smallest_multiple(4)
# [1] 12
# > Smallest_multiple(5)
# [1] 60
# > Smallest_multiple(6)
# [1] 60
# > Smallest_multiple(7)
# [1] 420
# > Smallest_multiple(8)
# [1] 840
# > Smallest_multiple(9)
# [1] 2520
# 思路：
# 1.列出20以内的质数，并求这些质数的小于20的最高次幂
# 2.再将这些质数的最高次幂的积相乘
Problem 6:Sum square difference
The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + … + 10^2 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)^2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
sum_of_squares <- function(num){
res = 0
for (i in 1:num) {
res <- res + i^2
}
return(res)
}
square_of_sums <- function(num){
return(sum(1:num)^2)
}
}
print(abs(sum_of_squares(100)-square_of_sums(100)))
Problem 7:10001st prime
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
search_prime <- function(search_num){
prime_judge <- function(num){
mark <-1
for (i in 2:(num-1)) {
if(num%%i==0){
mark <- 0
}
}
return(mark)
}
order = 1
i = 2
while(order < search_num){
i <- i + 1
if(prime_judge(i)){
order = order + 1
}
}
return(i)
}
t1<-Sys.time()
search_prime(10001)
# [1] 104743
t2<-Sys.time()
print(t2-t1)
# Time difference of 53.18486 mins
# 慢死人不偿命呀
# 总之上面的方法肯定是不科学的，即使答案是对的，要寻找质数的规律
# 学习pracma里面的函数，可能以后答题还是找现在有的函数比较好？
install.packages('pracma')
library(pracma)
x<-c(primes(10000000))
x
x[10001]
Some useful facts:
1 is not a prime.
All primes except 2 are odd.
All primes greater than 3 can be written in the form 6k+/-1.（看不懂）
Any number n can have only one primefactor greater than n .
The consequence for primality testing of a number n is: if we cannot find a number f less than or equal n that divides n then n is prime: the only primefactor of n is n itself
5,6,7题我已经尝试使用函数啦~虽然写的代码不是很高效，美观。
Problem 8：Largest product in a series
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
# 编写计算最大成绩的函数
max_multiply <- function(num){
digit_number <- "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
library(stringr)
digit_number_list <- (str_split(digit_number,pattern = "") %>% lapply(as.numeric))[[1]]
n <- length(digit_number_list) - num + 1
k <- 0
for (i in 1:n){
prod_res <- prod(digit_number_list[i:(i + num -1 )])
if (prod_res > k){
max_res <- prod_res
mark <- i
}else{
max_res <- k
}
k <- max_res
}
print(max_res)
print(digit_number_list[mark:(mark + num -1)])
}
# 对几个数进行相乘使用prod函数：
# https://stackoverflow.com/questions/3087145/multiplying-all-elements-of-a-vector-in-r
# 测试答案：
> max_multiply(13)
[1] 23514624000
[1] 5 5 7 6 6 8 9 6 6 4 8 9 5
> max_multiply(4)
[1] 5832
[1] 9 9 8 9
Problem 9:Special Pythagorean triplet
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
$a^2 + b^2 = c^2$
For example, $32 + 42 = 9 + 16 = 25 = 52$.
There exists exactly one Pythagorean triplet for which $a + b + c = 1000$. Find the product $abc$.
t1 <- Sys.time()
for (a in 1:1000){
for (b in 1:(1000-a)){
c <- sqrt(a*a + b*b)
if(a+b+c==1000){
cat(a,b,c,a*b*c,"\n")
}
}
}
t2 <- Sys.time()
t2-t1
# 200 375 425 31875000
# 375 200 425 31875000
# Time difference of 0.3160474 secs
Problem 10:Summation of primes
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
sum_prime <- function(max_num){
prime_judge <- function(num){
mark <-1
for (i in 2:(num-1)) {
if(num%%i==0){
mark <- 0
}
}
return(mark)
}
sum_num = 2
for (j in 2:max_num){
if(prime_judge(j)){
sum_num = sum_num + j
}
}
print(sum_num)
}
sum_prime(10)
# 注意上面的方法是非常慢的；
# 所以还是使用R包pracma
library(pracma)
sum((primes(10)))
sum((primes(2000000)))