题目58：考察螺旋网格中对角线上质数的数量

欧拉计划

Spiral primes

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.



It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

题目：

从 1 开始逆时针旋转，可以得到一个边长为 7 的螺旋正方形。



有趣的是奇数的平方数都处于右下对角线上。更有趣的是，对角线上的 13 个数字中有 8 个质数，其百分比是 8/13 ≈ 62%。

如果在上面的螺旋正方形上再加一层，可以得到一个边长为 9 的螺旋正方形。如果这个过程继续，到螺旋正方形的边长为多少时，对角线上的质数百分比第一次降到 10% 以下？

迷雾少年

边长为3的正方形的对角线质数有3个 质数百分比为0.333333
边长为5的正方形的对角线质数有5个 质数百分比为0.2
边长为7的正方形的对角线质数有8个 质数百分比为0.163265
边长为9的正方形的对角线质数有9个 质数百分比为0.111111
边长为11的正方形的对角线质数有10个 质数百分比为0.0826446
边长为13的正方形的对角线质数有11个 质数百分比为0.0650888
边长为15的正方形的对角线质数有13个 质数百分比为0.0577778
边长为17的正方形的对角线质数有15个 质数百分比为0.0519031
边长为19的正方形的对角线质数有16个 质数百分比为0.0443213
边长为21的正方形的对角线质数有18个 质数百分比为0.0408163
边长为23的正方形的对角线质数有19个 质数百分比为0.0359168
边长为25的正方形的对角线质数有21个 质数百分比为0.0336
边长为27的正方形的对角线质数有22个 质数百分比为0.0301783
边长为29的正方形的对角线质数有23个 质数百分比为0.0273484
边长为31的正方形的对角线质数有23个 质数百分比为0.0239334
边长为33的正方形的对角线质数有23个 质数百分比为0.0211203
边长为35的正方形的对角线质数有24个 质数百分比为0.0195918
边长为37的正方形的对角线质数有25个 质数百分比为0.0182615
边长为39的正方形的对角线质数有26个 质数百分比为0.017094
边长为41的正方形的对角线质数有27个 质数百分比为0.0160619
边长为43的正方形的对角线质数有28个 质数百分比为0.0151433
边长为45的正方形的对角线质数有28个 质数百分比为0.0138272
边长为47的正方形的对角线质数有28个 质数百分比为0.0126754
边长为49的正方形的对角线质数有28个 质数百分比为0.0116618
边长为51的正方形的对角线质数有29个 质数百分比为0.0111496
边长为53的正方形的对角线质数有29个 质数百分比为0.010324
边长为55的正方形的对角线质数有31个 质数百分比为0.0102479
边长为57的正方形的对角线质数有32个 质数百分比为0.00984918
边长为59的正方形的对角线质数有33个 质数百分比为0.00948003
边长为61的正方形的对角线质数有34个 质数百分比为0.00913733
边长为63的正方形的对角线质数有35个 质数百分比为0.00881834
边长为65的正方形的对角线质数有35个 质数百分比为0.00828402
边长为67的正方形的对角线质数有37个 质数百分比为0.00824237
边长为69的正方形的对角线质数有37个 质数百分比为0.00777148
边长为71的正方形的对角线质数有38个 质数百分比为0.00753819
边长为73的正方形的对角线质数有39个 质数百分比为0.00731845
边长为75的正方形的对角线质数有40个 质数百分比为0.00711111
边长为77的正方形的对角线质数有41个 质数百分比为0.00691516
边长为79的正方形的对角线质数有43个 质数百分比为0.00688992
边长为81的正方形的对角线质数有44个 质数百分比为0.00670629
边长为83的正方形的对角线质数有44个 质数百分比为0.00638699
边长为85的正方形的对角线质数有45个 质数百分比为0.00622837
边长为87的正方形的对角线质数有45个 质数百分比为0.0059453
边长为89的正方形的对角线质数有45个 质数百分比为0.0056811
边长为91的正方形的对角线质数有48个 质数百分比为0.0057964
边长为93的正方形的对角线质数有48个 质数百分比为0.00554977
边长为95的正方形的对角线质数有49个 质数百分比为0.00542936
边长为97的正方形的对角线质数有49个 质数百分比为0.00520778
边长为99的正方形的对角线质数有49个 质数百分比为0.00499949


辣鸡代码还调试了很久，，，，

1. #include "myLib/myLib.h"
   
2. #pragma comment(lib,"myLib//myLib.lib")
   
3. using namespace std;
   
4. 
   
5. 
   
6. //加入是n行n列 正方形  那么右下角的数字就是n*n   就是质数1-n*n
   
7. 
   
8. 
   
9. //建立一个n*n的矩阵 返回其中对角线质数个数
   
10. //建立的过程是个递归  从外到里  
    
11. //假设最大的变长1000
    
12. #define MAXC 1000
    
13. int arr[MAXC][MAXC]={0};
    
14. 
    
15. int hang = 7;
    
16. //建立
    
17. //m是第几列了
    
18. //startnum是左上角开始的数字
    
19. 
    
20. void jianli(int n,int m,int startnum)
    
21. {
    
22.         if(1==startnum)
    
23.         {
    
24.                 arr[n][n] = 1;
    
25.                 return ;
    
26.         }
    
27.         int temp=startnum;
    
28.         for (int z=0;z<m;z++)
    
29.         {
    
30.                         arr[n][n+z] = temp--;
    
31.         }
    
32.         temp=startnum;
    
33.         for (int z=0;z<m;z++)
    
34.         {
    
35.                 arr[n+z][n] = temp++;
    
36.         }
    
37.         temp=startnum+m-1;
    
38.         for (int z=0;z<m;z++)
    
39.         {
    
40.                 arr[n+m-1][n+z] = temp++;
    
41.         }
    
42.         temp=arr[n][n+m-1];
    
43.         for (int z=0;z<m-1;z++)
    
44.         {
    
45.                 arr[n+z][n+m-1] = temp--;
    
46.         }
    
47.         jianli(n+1,m-2,startnum-4*m+8);
    
48. }
    
49. 
    
50. //建立表后找出有多少个对角线质数
    
51. 
    
52. int gethow()
    
53. {
    
54.         int sum=0;
    
55.         for (int i = 0;i<hang;i++)
    
56.         {
    
57.                
    
58.                 //std::cout<<arr[i][i]<<" "<<endl;
    
59. 
    
60.                 if(iszhishu(arr[i][i]))
    
61.                         sum++;
    
62.         }
    
63.                 int lie  = hang;
    
64.                 for (int i = 0;i<hang;i++)
    
65.                 {
    
66.                         //std::cout<<arr[i][hang-i-1]<<" "<<endl;
    
67. 
    
68.                         if(iszhishu(arr[i][hang-i-1]))
    
69.                                 sum++;
    
70.                 }
    
71.         return sum;
    
72. }
    
73. /*
    
74. void clear()
    
75. {
    
76.         hang = 0;
    
77.         for (int n=0;n<MAXC;n++)
    
78.         {
    
79.                 for (int nm=0;nm<MAXC;nm++)
    
80.                 {
    
81.                         arr[n][nm] = 0;
    
82.                 }
    
83.         }
    
84. }*/
    
85. int main()
    
86. {
    
87.         //3行的正方形 开始的数字是5
    
88.         //3 5  3*3 - 4
    
89.         //5 17  5*5 -8
    
90.         //7 37  7*7 -12
    
91.         //开始数字= 边长平方 - 2*(变长-1)
    
92.         //表都建立了 接下来就easy了
    
93.          
    
94.         //std::cout<<gethow();
    
95.         for (int i = 3;i<=100;i+=2)
    
96.         {
    
97.                 double baifen=0;
    
98.                 hang = i;
    
99.                 jianli(0,i,i*i-2*(i-1));
    
100.                 std::cout<<"边长为"<<i<<"的正方形"<<"的对角线质数有"<<gethow()<<"个 ";
     
101.                 baifen = double(gethow() ) /  ((double)i*i);
     
102.                 std::cout<<"质数百分比为"<<baifen<<endl;
     
103.                 //clear();
     
104.         }
     
105.         return 0;
     
106. }

复制代码

jerryxjr1220

迷雾少年 发表于 2016-8-31 12:45
边长为3的正方形的对角线质数有3个 质数百分比为0.333333
边长为5的正方形的对角线质数有5个 质数百分比为 ...

题目理解错了，这个百分比不是对角线质数占所有数的百分比，是占对角线个数的百分比
正确的应该是26241

1. def isPrime(n):
   
2.         if n == 1: return False
   
3.         if n == 2 or n == 3: return True
   
4.         if n%2 == 0: return False
   
5.         for i in range(3,int(n**0.5+1),2):
   
6.                 if n%i == 0:
   
7.                         return False
   
8.         return True
   
9. 
   
10. crosslist = [0]*100000
    
11. for n in range(3,100000,2):
    
12.         cross = 2*n-1
    
13.         crossprime = 0
    
14.         if isPrime(n*n): crossprime += 1
    
15.         if isPrime(n*n-n+1): crossprime += 1
    
16.         if isPrime(n*n-2*n+2): crossprime += 1
    
17.         if isPrime(n*n-3*n+3): crossprime += 1
    
18.         crosslist[n] = crosslist[n-2]+crossprime
    
19.         if (float(crosslist[n]) / cross) < 0.1:
    
20.                 print (n)
    
21.                 exit()

复制代码

愤怒的大头菇

1. import math
   
2. def Prime(x):
   
3.     if x >1:
   
4.         if x==2:
   
5.             return True
   
6.         if x%2==0:
   
7.             return False
   
8.         for i in range(3,int(math.sqrt(x)+1),2):
   
9.             if x%i==0:
   
10.                 return False
    
11.         return True
    
12.     return False
    
13. list1=[1];total = 1;count = 0;floor = 1;i = 1
    
14. while True:
    
15.     i += 2
    
16.     floor += 1
    
17.     if Prime(i**2):
    
18.         count += 1
    
19.     if Prime(i**2-(i-1)):
    
20.         count += 1
    
21.     if Prime(i**2-(i-1)*2):
    
22.         count += 1
    
23.     if Prime(i**2-(i-1)*3):
    
24.         count += 1
    
25.     total += 4
    
26.     if count /total <0.1:
    
27.         break
    
28. print(i

复制代码

结果：26241

芒果加黄桃

1. # encoding:utf-8
   
2. # 计算对角线质数比例
   
3. from time import time
   
4. from math import sqrt
   
5. def getPrimes(N):
   
6.     primes = [True] * N
   
7.     primes[0], primes[1] = False, False
   
8.     for i, prime in enumerate(primes):
   
9.         if prime:
   
10.             for j in range(i * i, N, i):
    
11.                 primes[j] = False
    
12.     return [k for k, p in enumerate(primes) if p ]
    
13. def isPrime(n, l_pr):
    
14.     # 不考虑1
    
15.     if n < 4:
    
16.         return True
    
17.     if n % 2 == 0 or n % 3 == 0 :
    
18.         return False
    
19.     t = int(sqrt(n))
    
20.     for i in l_pr:
    
21.         if i > t:
    
22.             return True
    
23.         if n % i == 0:
    
24.             return False
    
25.     return True
    
26. def euler058(N=100000):
    
27.     n_chprimes, step, num = 0, 0, 1
    
28.     l_primes = getPrimes(N)
    
29.     while True:
    
30.         step += 2
    
31.         for i in range(1, 5):
    
32.             num += step
    
33.             flag = isPrime(num, l_primes)
    
34.             if flag:
    
35.                 n_chprimes += 1
    
36.         if n_chprimes / (2 * step + 1) < 0.10:
    
37.             print(step + 1, n_chprimes / (2 * step + 1))
    
38.             break
    
39. if __name__ == '__main__':
    
40.     start = time()
    
41.     euler058()
    
42.     print('cost %.6f sec' % (time() - start))
    

复制代码

26241 0.09999809454850327
cost 2.233223 sec

飘飞的白杨

1. def isprime(n):
   
2.     '''判断是否是素数'''
   
3.     if n <= 1: return False
   
4.     if n == 2 or n == 3: return True
   
5.     if n % 2 == 0: return False
   
6.     for i in range(3, int(n**0.5)+1, 2):
   
7.         if n % i == 0: return False
   
8.     return True
   
9. num = 0
   
10. for i in range(3, 100000, 2):
    
11.     if isprime(i*i-(i-1)): num += 1
    
12.     if isprime(i*i-2*(i-1)): num += 1
    
13.     if isprime(i*i-3*(i-1)): num += 1
    
14.     if num/(i*2-1) < 0.1: break
    
15. print(i)

复制代码

改

1. def primes(N):
   
2.     '''素数表'''
   
3.     l =  int(N**0.5) + 1
   
4.     prime = [False, False] + [True] * N
   
5.     for i in range(2, l):
   
6.         if prime[i]:
   
7.             for j in range(2, N//i + 1):
   
8.                 if prime[j*i]:
   
9.                     prime[j*i] = False
   
10.     return tuple(i for i in range(len(prime)) if prime[i])
    
11. def isprime(n):
    
12.     '''判断是否是素数'''
    
13.     if n <= 1: return False
    
14.     if n == 2: return True
    
15.     for i in primes_tuple:
    
16.         if i*i > n: return True
    
17.         if n % i == 0: return False
    
18.     for i in range(primes_tuple[-1]+2, int(n**0.5)+1, 2):
    
19.         if n % i == 0: return False
    
20.     return True
    
21. X, num = 100000, 0
    
22. primes_tuple = primes(X)
    
23. for i in range(3, X, 2):
    
24.     if isprime(i*i-(i-1)): num += 1
    
25.     if isprime(i*i-2*(i-1)): num += 1
    
26.     if isprime(i*i-3*(i-1)): num += 1
    
27.     if num/(i*2-1) < 0.1: break
    
28. print(i)

复制代码

najin

用的matlab
结果是
       26241

时间已过 4.395559 秒。
>>

刚开始写了函数直接生成螺旋矩阵，算不出来；
后来换了解法，但是判断素数又耗时太长，最后用了这个办法

hk1057

import time


def time_it():
        start=time.time()
        fun()
        end=time.time()
        print('cost %.6f Secs'%(end-start))


def is_prime(num):
        if num <= 1:
                return False
        if num == 2:
                return True
        if num % 2 == 0:
                return False
        for i in range(3,int(num**0.5)+1,2):
                if num % i == 0:
                        return False
        else:
                return True
       
       
def fun():
        start=3
        list1=[1]
        list2=[]
        while True:
                for x in range(4):
                        list1.append(start**2-(start-1)*x)
                       
                for each in list1[-4:]:
                        if is_prime(each):
                                list2.append(each)
               
                if len(list2)/len(list1) < 0.1:
                        print('第一个质数百分比<10%%的螺旋正方形的边长为%d'%start)
                        break
                else:
                        start+=2
                       

if __name__=='__main__':
        time_it()
'''
第一个质数百分比<10%的螺旋正方形的边长为26241
cost 2.991065 Secs
'''

王小召

结果：26241
用时：6.7392432 秒

1. import time
   
2. 
   
3. def is_prime(num):
   
4.     if not num % 2 or not num % 3:
   
5.         return False
   
6.     else:
   
7.         for i in range(2, int(num**0.5) + 1, 1):
   
8.             if not num % i:
   
9.                 return False
   
10.         return True
    
11. 
    
12. 
    
13. def cal():
    
14.     fenzi = 8
    
15.     l = 7
    
16.     while fenzi/(2*l - 1) > 0.1:
    
17.         l += 2
    
18.         count = 0
    
19.         if is_prime(l ** 2):
    
20.             count += 1
    
21.         if is_prime(l ** 2 - (l - 1)):
    
22.             count += 1
    
23.         if is_prime(l ** 2 - 2 * (l - 1)):
    
24.             count += 1
    
25.         if is_prime(l ** 2 - 3 * (l - 1)):
    
26.             count += 1
    
27.         fenzi += count
    
28.     else:
    
29.         return l
    
30. print("结果：{}\n用时：{} 秒".format(cal(), time.process_time()))

复制代码

debuggerzh

26241

Process returned 0 (0x0)   execution time : 0.470 s
Press any key to continue.
欧拉筛，找规律，线性递推

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. 
   
5. const int M = 1e5;
   
6. int ct = 0;
   
7. bool prime[M];
   
8. int factor[M];
   
9. 
   
10. void euler_sieve(){
    
11.   prime[1] = false;
    
12.   for (int i = 2;i <= M;i++) prime[i] = true;
    
13. 
    
14.   for (int i = 2;i <= M;i++){
    
15.     if (prime[i]) factor[++ct] = i;
    
16.     for (int j = 1;j <= ct && i*factor[j] < M;j++){
    
17.       prime[i*factor[j]] = false;
    
18.       if (i % factor[j] == 0) break;
    
19.     }
    
20.   }
    
21. }
    
22. 
    
23. bool isprime(int x){
    
24.   for (int i = 1;factor[i] <= sqrt(x);i++){
    
25.     if (x % factor[i] == 0) return false;
    
26.   }
    
27.   return true;
    
28. }
    
29. 
    
30. int main(){
    
31.   euler_sieve();
    
32.   int prime_num = 0;
    
33. 
    
34.   for (int n = 3; ;n+=2){
    
35.     int tot = 2*n - 1;
    
36.     int ini = n*n - 3*n + 3;
    
37. 
    
38.     for (int i = 0;i < 3;i++){
    
39.       bool b = ini < M ? prime[ini] : isprime(ini);
    
40.       if (b) prime_num++;
    
41. 
    
42.       ini += n-1;
    
43.     }//免去对平方数的判断
    
44.     if ( (double)prime_num / tot < 0.1 )  {cout << n << endl;  break;}
    
45.   }
    
46. 
    
47.   return 0;
    
48. }
    

复制代码

4444567

26241 0.09999809454850327

1. from time import time
   
2. def prime(n):
   
3.     if n<= 1:
   
4.         return False
   
5.     else:
   
6.         if n==2 or n==3:
   
7.             return True
   
8.         if n>3:
   
9.             for i in range(3,int(n**0.5)+1,2):
   
10.                 if n%i == 0:
    
11.                     return False
    
12.             return True
    
13. t = time()
    
14. b = 1     #边长,每次+2
    
15. djx = 1   #对角线上数字个数，每次+4
    
16. c = 1     #初始数字1
    
17. d = 0    #递增数
    
18. l1= []   #处于对角线的质数，四次为一个周期，2，4，6递增
    
19. while True:
    
20.     a = 1  #周期指针
    
21.     b += 2
    
22.     d += 2
    
23.     djx += 4
    
24.     while a<5:
    
25.         c += d
    
26.         if prime(c):
    
27.             l1.append(c)
    
28.         a += 1
    
29.     if len(l1)/djx < 0.1:
    
30.         print(b, len(l1)/djx)
    
31.         print('\n',time()-t)
    
32.         break
    
33.    
    

复制代码

6.351067543029785