题目12：第一个拥有超过500个约数的三角形数是多少？,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

DetConan 发表于 2018-9-4 15:12:34

python3 结果是：76576500
时间:0.970447 s
import time

start = time.clock()
def get_divisors_num(n, prime):
num = 1
count = 1
while (n > 1):
   for p in prime:
         while(n % p == 0):
            count += 1
            n = n // p
         num *= count
         count = 1
         if n == 1:
            break
return num

def get_primes(number):
# '筛法找出所有质数，并求和'
list_primes = * (number + 1)
list_primes = False
list_primes = False
for i in range(2, number):
   if list_primes:
         for j in range(i ** 2, number, i):
            list_primes = False
list_result = []
for k in range(2, number):
   if list_primes:
         list_result.append(k)
return list_result

prime = get_primes(100000)
n = 1
while 1:
n += 1
s = n * (n - 1) // 2
if get_divisors_num(s, prime) > 500:
   break
print(s)

end = time.clock()
print("read:%f s" % (end - start))

山有扶苏啊 发表于 2018-10-19 15:34:57

from math import sqrt
def count(n):
t = 0
for i in range(1, n+1):
   t += i
return t

for r in range(10000000):
s = count(r)
result = []
for i in range(1, int(sqrt(s))+1):
   if s%i == 0:
         result.append(i)
if len(result) > 250:
   print(s)
   print(len(result))
   break

76576500

cwhsmile 发表于 2019-4-25 16:17:22

import time
import math
import functools

def test1():
num = 1
count = 0#约数个数
li = []
while len(li) < 500:
   count = 0
   li = []
   if num%2 == 0:
         sjx_num = (num+1)*(num//2)
         if sjx_num%2 == 0:
            i = 1
            j = 4
            while i < j:
               if sjx_num%i == 0:
                     j = sjx_num//i
                     li.extend()
               i += 1

         else:
            i = 1
            j = 4
            while i < j:
               if sjx_num%i == 0:
                     j = sjx_num//i
                     li.extend()
               i += 2

   else:
         sjx_num = num*(num//2) + num
         if sjx_num%2 == 0:
            i = 1
            j = 4
            while i < j:
               if sjx_num%i == 0:
                     j = sjx_num//i
                     li.extend()
               i += 1

         else:
            i = 1
            j = 4
            while i < j:
               if sjx_num%i == 0:
                     j = sjx_num//i
                     li.extend()
               i += 2


   num += 1


return sjx_num,num-1

start = time.perf_counter()

print(test1())
end = time.perf_counter()
print(end-start)

永恒的蓝色梦想 发表于 2019-8-3 19:45:12

本帖最后由永恒的蓝色梦想于 2020-5-9 17:31 编辑

None

1666194196 发表于 2019-10-12 11:27:05

#include <stdio.h>
void main(){
//高度可约的三角形数
//三角形数数列是通过逐个加上自然数来生成的。
//例如，第7个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。三角形数数列的前十项分别是：
//1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
//让我们列举出前七个三角形数的所有约数：
//1: 1 // 3: 1,3 // 6: 1,2,3,6 //10: 1,2,5,10 //15: 1,3,5,15 //21: 1,3,7,21 //28: 1,2,4,7,14,28
//我们可以看出，28是第一个拥有超过5个约数的三角形数。
//第一个拥有超过500个约数的三角形数是多少？

int i=1,count=0;//i:从 1循环到无穷的数，count：记录三角形数有几个因数
long sum=0; //sum:i的和（三角形数）
while(1){
sum+=i;//计算出三角形数
int j;
for(j=1;j<=sum;j++){//从 1到这个三角形数的循环
if(sum%j==0){//找能整除的数的个数（因数个数）
count++;//如果能整除说明是因数，count+1
}
}
printf("三角形数：%d,有%d个因数\n",sum,count);//看count到几了

if(count>5){//大于5，就输出这个三角形数，跳出 while循环（大于500同理）
printf("超过5个约数的三角形数：%d",sum);
break;
}else{//count记录完上一个三角形数后，要清零记录下一个
count=0;
}
i++;
}
}

代号-K 发表于 2020-3-12 21:15:25

发现与素数都离不开关系
void getApproximation(int *answer, int flag, int stop)
{
int array = {0};
int temp = {0};
array = 2;
int i = 1;

int j = 3;
int k = 0;

bool yes = 1;
while(true)
{
   if(i == flag)
   {
         break;
   }
   else
   {
         k = 0;
         while( k < i)
         {
            if(j % array == 0)
            {
               yes = 0;
               break;
            }
            k++;
         }
         if(yes)
         {
            array = j;
         }
   }
   j += 2;
   yes = 1;
}

j = 1;
while(true)
{
   j++;
   yes = 1;
   *answer = 1;
   // construct trigle
   int value = 0;
   int sum = 0;
   sum = (j*(j+1))/2;
   value = sum;
   //printf("temp:1->%d = %d\t", j, value);
   // calculate this number approximation

   k = 0;
   while(k < i)
   {
         // judge is union
         while(sum % array == 0)
         {
            temp-1] += 1;
            sum /= array;
            yes = 0;
         }
         // put next prime to compare
         if(sum > array)
         {
            k++;
         }else
         {
            break;
         }
   }
   if(yes)
   {
         temp = 1;
   }
   for(k = 0; k < array; k++)
   {
         //printf("%d\n", temp);
         if(temp > 0)
         {
            *answer *= (temp + 1);
         }
         temp = 0;
   }
   //printf("choice:%d\n", *answer);
   //break;
   if(*answer >= stop)
   {
         printf("over:%d\n", value);
         break;
   }
}
}
int main(int argc, char *argv[])
{
//ElementTyperet;
int ret;
getApproximation(&ret, 100000, 500);
printf("answer:%d\n", ret);
//test();
return 0;
}

代号-K 发表于 2020-3-13 23:57:36

想复杂了，简单的{:10_249:}
void getApproximationImprove(ElementType *answer, int flag)
{
ElementType start = 1;
ElementType sum = 0;
ElementType numTemp;
int count = 0;
while(true){
   count = 0;
   sum = start*(start+1)/2;
   for(numTemp = 1; numTemp <= (ElementType) pow(sum, 0.5);numTemp++)
   {
         if(sum % numTemp == 0) count++;
   }
   *answer = sum;
   if(2*count >= flag){
         printf("%d\t%lld\t",2*count,start);
         return;
   }
   start++;
}
}

int main(int argc, char *argv[]){
//ElementTyperet;
ElementType ret = -1;
getApproximationImprove(&ret,500);
printf("answer:%lld\n", ret);
return 0;
}

永恒的蓝色梦想 发表于 2020-4-19 18:50:30

本帖最后由永恒的蓝色梦想于 2020-5-9 18:14 编辑

C++ 251ms#include<iostream>
#include<cmath>
using namespace std;

int main() {
int i, j = 1, count = 0, k;
double root;

for (i = 1;; i += ++j) {
   root = sqrt(i);
   count = 0;

   for (k = 2; k < root; ++k) {
         if (!(i % k)) {
            ++count;
         }
   }

   if (count > (fmod(root, 1) ? 249 : 250)) {
         cout << i << endl;
         return 0;
   }
}
}

leon0149 发表于 2020-5-9 16:37:07

本帖最后由 leon0149 于 2020-5-14 22:03 编辑

76576500
0.105 s
#include <stdio.h>
#include <time.h>

int main(void) {
int num = 1;
int i = 2;
int cnt = 0;

clock_t start, finish;
double duration;
start = clock();

while (cnt < 500) {
   cnt = 0;
   num += i;
   for (int j = 1; j *j <= num; ++j) {
         if (num % j == 0) {
            if (j * j == num) {
               cnt++;
            } else {
               cnt += 2;
            }
         }
   }
   i++;
}

printf("%d\n", num);

finish = clock();
duration = (double)(finish - start)/CLOCKS_PER_SEC;
printf("%.3f s", duration);

return 0;
}

有马_冬巳 发表于 2020-10-6 15:59:53

'''三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是：
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
下面我们列出前七个三角形数的约数：
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
可以看出 28 是第一个拥有超过 5 个约数的三角形数。
那么第一个拥有超过 500 个约数的三角形数是多少？'''

def trinum(num_of_divisors):
end_num = 1
sum = 0
Num_of_divisors = 0

while Num_of_divisors < num_of_divisors:
   Num_of_divisors = 0
   sum += end_num

   if math.sqrt(sum) == int(math.sqrt(sum)):
         Num_of_divisors += 1

   for divisors in range(1,int(math.sqrt(sum))):
         if sum % divisors == 0:
            Num_of_divisors += 2

   end_num += 1

print("第一个拥有超过500个约数的三角形数是: %d" %sum)
print("一共有%d个约数" %Num_of_divisors)

start_trinum = time.time()
trinum(500)
time_trinum = time.time() - start_trinum
print("%f秒" %time_trinum)

第一个拥有超过500个约数的三角形数是: 76576500
一共有576个约数
3.206136秒

gonorth 发表于 2020-11-5 18:33:47

import math as m
import datetime as dt

def div():
record = []
count = 0
n = 0
while 1 :
   count += 1
   n += count
   for each in range(1, int(m.sqrt(n))+ 1):
         if n % each == 0:
            record.append(each)
   if len(record) > 250:
         print (n)
         print (count)
         break
   record = []
start = dt.datetime.now()
div()
end = dt.datetime.now()
print ("用时" , end - start)

a1351468657 发表于 2021-3-6 21:50:34

#include <stdio.h>
#include <math.h>

main()
{
int i, j = 2, k, num = 1, count = 0;
while (1)
{
num += j;
j++;
k = sqrt(num);
for (i = 2; i <= k; i++)
{
if (num % i == 0)
{
if (i * i == num)
{
count++;
}
else
{
count += 2;
}
}
}
if (count + 2 > 500)
{
break;
}
count = 0;
}
printf("第一个超过500个约数的三角数是：%d\n", num);
}

若有错误，望大佬纠正！

卢本伟牛逼 发表于 2021-8-12 23:41:36

本帖最后由卢本伟牛逼于 2021-8-12 23:47 编辑

#include <stdio.h>
#include <math.h>

int count = 0;

int count_fact(int value)
{
int i;
int flag = 0;
for(i=1;i<sqrt(value) + 1;i++)
{
count += 1;
if (value%i==0) flag += 2;
}
return flag;
}

int count_fact2(int value)
{
int i;
int result = 1;
int flag;
if (value <= 2) return 0;
for(i=2; i<=value; i++){
flag = 0;
count += 1;
while(value % i == 0){
flag += 1;
value /= i;
}
if (flag!=0){
result *= (flag + 1);
}
}
return (result == 1)?0:result;
}

int main(void)
{
int i=1;

while(count_fact2((i+1)*i/2) < 500) i++;

printf("result = %d\n", (i+1)*i/2);
printf("count = %d\n", count);

return 0;
}
//count_fact result = 76576500
//count_fact count= 54157266

//count_fact2 result = 76576500
//count_fact2 count= 26736502

番杰发表于 2021-10-29 10:06:17

#include<stdio.h>

int main(void)
{
unsigned int sum = 0,num = 0;

for(int i = 1;;i++)
{
sum += i;
for(int j = 1;j <= num ;j++)
{
if(num % j == 0)
{
num++;
}
}
if(num >= 500)
{
break;
}
}

printf("%d",sum);

return 0;
}

弈秋呜呜呜 发表于 2021-11-20 16:06:47

0.2s

#include <stdio.h>

int main(void)
{
long res = 0;
long i = 1,j,temp;
int count = 0;

while (1)
{
res += i;
i++;
for(j = 1;j < res;j++)
{
temp = res/j;
if (temp < j)
break;
if (temp * j == res)
count += 2;
}
if (count >= 500)
{
printf("%ld\n",res);
return 0;
}
count = 0;
}
}

jerryxjr1220 发表于 2022-2-24 00:15:31

package main

import (
"fmt"
"time"
)

//题目：
//
//三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是：
//
//1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
//
//下面我们列出前七个三角形数的约数：
//
//1: 1
//3: 1,3
//6: 1,2,3,6
//10: 1,2,5,10
//15: 1,3,5,15
//21: 1,3,7,21
//28: 1,2,4,7,14,28
//可以看出 28 是第一个拥有超过 5 个约数的三角形数。
//
//那么第一个拥有超过 500 个约数的三角形数是多少？

func yueshu(a int32) int32 {
n := make(mapint32)
for {
if a > 1 {
var i int32
for i = 2; i <= a; i++ {
if a%i == 0 {
n++
a /= i
break
}
}
} else {
res := int32(1)
for _, value := range n {
res *= (value + 1)
}
return res
}

}
}

func triangle(n int32) int32 {
return (1 + n) * n / 2
}

func main() {
t := time.Now()
var i int32 = 1
for {
if yueshu(triangle(i)) > 500 {
fmt.Println(triangle(i))
break
}
i++
}
tt := time.Now()
fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}
输出：
GOROOT=C:\Program Files\Go #gosetup
GOPATH=C:\Users\Administrator\go #gosetup
"C:\Program Files\Go\bin\go.exe" build -o C:\Users\Administrator\AppData\Local\Temp\GoLand\___go_build_Euler12_go.exe C:\Users\Administrator\Documents\GoProject\src\Euler12.go #gosetup
C:\Users\Administrator\AppData\Local\Temp\GoLand\___go_build_Euler12_go.exe
76576500
耗时： 42 ms

进程已完成，退出代码为 0

jerryxjr1220 发表于 2022-2-24 00:17:08

Asss-whom 发表于 2022-8-9 21:09:15

本帖最后由 Asss-whom 于 2022-8-9 21:17 编辑

use primes::factors_uniq;

pub fn run() -> Result<(), Box<dyn std::error::Error>> {
for i in 1.. {
   let num = i * (i + 1) / 2;
   let f = factor(num);
   if f > 500 {
         println!("num = {num}, factors = {f}");
         break;
   }
}
Ok(())
}

fn factor(num: u64) -> i32 {
let f = factors_uniq(num);
f.into_iter()
   .map(|i| {
         let mut n = num;
         let mut count = 0;
         while n % i == 0 {
            n = n / i;
            count += 1
         }
         count
   })
   .fold(1, |acc, x| acc * (x + 1))
}

num = 76576500, factors = 576

TLM 发表于 2022-12-19 19:00:19

本帖最后由 TLM 于 2022-12-19 19:02 编辑

## python
import time
tt=time.time()
# an=n(n+1)/2
# 这个算法的时间复杂度应该是O(nlog(n)),其中n是第n个数，也就是n=O(an**0.5)
# 数学能力有限，不知道和目标数据之间的联系
# 通过列表，获得所有小于等于n+1的数的约数个数
def getNlist(n):
# 时间复杂度为O(nlog(n))这个是测试的，没计算
nlist=
for i in range(1,int(n**0.5)+1):
   for j in range(i,n+1):
         if i*j<=n:
            if i==j:# i为其约数
               nlist=nlist+1
            else:# i,j都是其约数
               nlist=nlist+2
         else:
            break
return nlist

def getminn(nlist,mubiao):
# O(n)
for i in range(len(nlist)-1):
   if i%2==1:
         # an=n(n+1)/2,拆成两个n和(n+1)/2这样的结构，最大公约数为1，只有一个相同的约数
         # 排列组合形成an的约数。这是整个算法中最精髓的
         if nlist[(i+1)//2-1]*nlist>=mubiao:
            return False,i+1
   else:
         if nlist*nlist[(i+2)//2-1]>=mubiao:
            return False,i+1
return True,0
# 目标值
mubiao=500
n=mubiao
data=(True,0)
while data:
nlist=getNlist(n)
data=getminn(nlist,mubiao)
# print(n)
# print(nlist)
# 找不到就放大列表，倍率放大寻找更快
n=n*2
print(data)# 第几个
print(data*(data+1)/2)# 三角数
print(time.time()-tt)
44ms

QLYYLQ 发表于 2023-7-27 17:21:06

本帖最后由 QLYYLQ 于 2023-7-27 17:33 编辑

#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<time.h>
#define NUMBER 200
bool a={1,1,0}/*当下标对应的数组元素为0的时候，下标是素数*/;
int b = {2,0};/*储存素数*/
void sushu(bool a[], int b[])
{
int i=2;
int j=1;
while(i<NUMBER)
{
   int i1 = 2*i;
   for(;i1<NUMBER;i1+=i) a=1;
   i++;
   while(i<NUMBER && a==1) i++;
   b=i;
   j++;
}
}
int sum(int i)
{
return (i*(i+1))/2;
}
int jieda(int sum1,int b[])
{
/*分解质因数*/
int c={0};
for(int i=0;i<35;i++)
{
   while(sum1%b==0)
   {
         c+=1;
         sum1/=b;
   }
}
/*计算因数个数*/
int j=0;
int answer =1;
while(j<35)
{
   if(c != 0) answer*=(c+1);
   j++;

}
return (answer);
}
int main()
{
clock_t finish,start;
start=clock();
sushu(a,b);
for(int i =100;i<20000;i++)
{
   if(jieda(sum(i),b)>=500)
   {
         printf("%d\n",sum(i));
         break;
   }
}
finish=clock();
double duration= (double)(finish - start)/CLOCKS_PER_SEC;
printf("%.3f",duration);
system("pause");
return 0;

}

时间是0.06s

这是用C语言写的
首先是用一个欧拉筛来筛选出来需要的素数，再通过质因数来计算因数个数
我的理解是这样的：一个数可以被分解成一连串的素数相乘，那么它的所有因数就是通过质因数不同组合后相乘得到的，比如：24=2*2*2*3，那么24的因数就是1，24； 3，8； 4，6； 2，14；其实都是2，2，2，3的不同组合，比如这里是2的三次方，那么我们就应该有四种选择（不选，选一个，选两个...）来组成一个因数，同理三也是，所以24的因数个数就是（3+1）*（1+1）=8个

页: 1 [2]

鱼C论坛's Archiver