求质数的题
在1，0交替出现且以1打头和结尾的所有正整数（如101，10101，1010101）中有多少个质数？求出所有质数。
参考答案:只有一个--101.
证明过程如下:
假设有n个1的数为An,首先A1是一个质数,下面证明当n≥2时An均为合数.
当n为偶数时,显然An能被101整除.
当n为奇数时,我们先看看An*11等于多少,也就是将An向前平移一位后与原数相加,即111…1(共2n个1),再将它乘以9得999…9(共2n个9),即10的2n次方减1(以下用10^2n表示10的2n次方),即An=(10^2n-1)/99.
而由因式分解得An=(10^n+1)(10^n-1)/99
=[(10^n+1)/11]*[(10^n-1)/9]
设前一个方括号内的数为a,后一个为b,显然b是整数,而一个数被11整除的充要条件是奇偶位和的差能被11整除,而10^n+1的奇数位和为1,偶数位和也为1,所以能被11整除,所以a也是一个不为1的整数,所以An就被分解了,所以An不是质数.
举个例子:
1010101010101=(10^14-1)/99
=[(10^7-1)/9]*[(10^7+1/11)]
=1111111*909091