python 6857
取约数算法优化 只取质数 记录取到的约数 i下次取约数从 i 开始
手写个轮子用来计时 优化效果很有限 可能要更大的数才见效
>>> timef(p3(),number=10000)
0.0010133860000109962
>>> timef(p3_mix(),number=10000)
0.000952252999979919
def p3_mix():
import math
a = 600851475143
def p3_get_prime(n):
return int(3*n+1+(math.sin(math.pi*n/2))**2)
def is_prime(n):
if not n%2:
return False
n1 = int(math.sqrt(n))
for i in range(3,n1+1,2):
if not n%i:
return False
return True
def p3_1_mix(n,num=1,i=2):
if is_prime(n):
return n
while i < a//2+1:
if not n%i:# n被i整除
return p3_1_mix(n/i,num,i)
else:# n无法被i整除
if i == 2:
i = 3
elif i == 3:
i = p3_get_prime(num)
else:
num += 1
i=p3_get_prime(num)
print(p3_1_mix(a))
冷钟天 发表于 2016-7-4 15:57
n=600851475143
a=2
while n!=a:
1，为什么a递增以后的值，没有在素数范围内也行？？？
2，为什么不断缩小的n，不再使用比a小的值（素数）取商？？？
假如n初始为100，a初始为2：
n a
1， 100 2<--素数
2、 50 3<--素数
3、 50 4
4、 50 5<--素数
5， 10 6
6， 10 7<--素数
7， 10 8
8， 10 9
9， 10 10
11才是质数啊？？？
C 不知道为啥不稳定 难道是虚拟机的原因？
#include<stdio.h>
int a;
int main(){
int i,j;
for(i = 2; i <= 500000;i++){
for(j = i * 2;j <=1000000;j += i)
a = 1;
}
for(i = 999999;i >= 2; i-- )
if(a == 0 && 600851475143%i == 0){
printf("%d",i);
return 0;
}
printf("600851475143");
return 0;
}
% %Euler_3What is the largest prime factor of the number 600851475143 ?
% % The prime factors of 13195 are 5, 7, 13 and 29.
x=input('please input a number\n');
l=0;
for i=3:2:x
if isprime(i)==1 && mod(x,i)==0
l=i;
x=x/i;
disp(l);
end
end
本帖最后由 永恒的蓝色梦想 于 2020-7-30 13:20 编辑
num = 600851475143
divisor = 3
while num != 1:
if num % divisor:
divisor += 2
else:
num //= divisor
print(divisor)
#include <stdio.h>
#include <time.h>
#include <math.h>
int main()
{
int begin_time, end_time;
begin_time = clock();
int biggest = 0;
_Bool not_prime = 0;
for (int i = 3; i < sqrt(600851475143); i += 2)
{
if (600851475143 % i == 0)
{
for (int j = 3; j < sqrt(i); j += 2)
{
if (i % j == 0)
{
not_prime = 1;
break;
}
}
if (!not_prime)
{
biggest = i;
}
}
}
printf("600851475143 的最大质数因子是%d\n", biggest);
end_time = clock();
printf("\n程序一共运行%dms\n", end_time - begin_time);
return 0;
}
#include <stdio.h>
#include <time.h>
int main()
{
unsigned long long num = 600851475143;
unsigned long long a, t;
int begin = clock();
for (a = 2; a < num; a++)
{
for (t = 2; t < a / 2; t++)
if (a % t == 0)
break;
if ( t >= a / 2)
if (num % a == 0)
{
num /= a;
a = 1;
}
}
printf("600851475143 最大质数因子 = %llu\n", num);
int end = clock();
printf("time = %dms\n", end - begin);
system("pause");
return 0;
}
import re
import math
import time
method = re.compile("[^0-9]")
def forma(miao):
tim = list()
ge_m = float("{:.10f}".format(miao))
ge_h = float("{:.10f}".format(ge_m / 3600))
ge_h_guo = float("{:.10f}".format(miao % 3600))
ge_f = float("{:.10f}".format(ge_h_guo / 60))
ge_miao = float("{:.10f}".format(ge_h_guo % 60))
if ge_h > 1:
tim.append(int(ge_h))
if ge_f > 1 or len(tim) != 0:
tim.append(int(ge_f))
tim.append(ge_miao)
return tim
da = int()
ran = input("请输入一个整数 , 求最大的质数因子：")
tex = method.search(ran)
if not tex:
ship = int(ran)#600851475143
chu = int(math.sqrt(ship))
time_start = time.perf_counter()
tiger_chu = sorted( , reverse = True)
rabbit_zhi = [ for each in sorted(tiger_chu , reverse = True)]
da = tiger_chu)]
miao = time.perf_counter() - time_start
lai = forma(miao)
if len(lai) == 1:
print("最大值为：" + str(da) + "\n运行时间为：{:.2f}秒".format(lai))
elif len(lai) == 2:
print("最大值为：" + str(da) + "\n运行时间为：{}分{}秒".format(lai , lai))
else:
print("最大值为：" + str(da) + "\n运行时间为：{}时{}分{}秒".format(lai , lai , lai))
else:
print("您输入的数值运行不了~~")
{:10_256:}#我感觉我的效率还不错，欢迎大家来copy~~
import tkinter as tk
x = 600851475143
i = 2
while True:
if i >= x:#当i > x时，x铁定除不尽i(当i = x 时，它就没意义了)，所以执行下列命令：
break
while x % i == 0: #当x % i == 0
if i >= x:#当i > x时，x铁定除不尽i(当i = x 时，它就没意义了)，所以执行下列命令：
break
else:
x /= i
else:
i += 1
s = tk.Tk();tk.Label(s,text=x).pack();s.mainloop() #显示出答案
#include <stdio.h>
void main(){
//13195的所有质因数为5、7、13和29。
//600851475143最大的质因数是？
int i,a=13195,max=0;
for(i=2;i<a;i++){//2到它本身-1的循环
if(a%i==0){//如果能整除说明是他的因数
int j,flag=1;
for(j=2;j<i;j++){//2到它本身-1的循环
if(i%j==0){//如果能整除说明有因数 ,标志为假 ，不输出
flag=0;
}
}
if(flag){//如果没有能整除顺序执行下来flag=1，为真。打印出这个数
printf("质因数%d\n",i);
max=i;
}
}
}
printf("做大质因数=%d",max);
}
本帖最后由 带上面具的孩纸 于 2019-10-19 11:51 编辑
int main()
{
unsigned long long int MPX;
int MAX = 1;
int i;
printf("\nplease input number: ");
scanf("%llu",&MPX);
for(i = 2;i < MPX;i++)
{
if(MPX % i == 0)
{
MAX = MAX > i ? MAX : i;
// printf("%d\t",i);
}
}
printf("\n MAX=%d\n",MAX);
return 0;
}
如有错误 请指正
unsigned long long isprime(unsigned long long num)
{
unsigned long long max=0;
for(unsigned long long i=2;i<=(int)sqrt((double)num);i++)
{
if( (num%i)==0 ){return 0;}
}
return 1;
}
unsigned long long max_factor(unsigned long long num)
{
unsigned long long max=0,temp=0;
for(unsigned long long j=2;j<=(int)sqrt((double)num);j++)
{
int n=0;
if(num%j==0) // 找出合数中的因子
{
if( isprime(j)==1 )
{
if(max<j){max=j;printf("prime=%llu\n",j);}
}
temp=num/j;
if( isprime(temp)==1 )
{
if(max<temp){max=temp;printf("prime=%llu\n",temp);}
}
}
}
return max;
}
游客 218.17.207.x 发表于 2015-10-30 16:07
大数用了__int64类型
输出结果：
非常感谢您的分享，请教您一下，我在linux环境下运行您的这段代码提示：unknowntypename '__int64',头文件<math.h>也包含了，问题在哪里了？{:5_110:}
#include <stdio.h>
#include <time.h>
int main(void)
{
int i = 2;
long int a = 600851475143;
time_t start, end;
time(&start);
while(a > 1)
{
if(a % i == 0)
{
a /= i;
continue;
}
i++;
}
time(&end);
printf("%ld的最大质因数为:%d\n", a, i);
printf("time:%ld\n", end - start);
return 0;
}
~
#include <stdio.h>
#include <time.h>
int main(void)
{
int i = 2;
long int a = 600851475143;
time_t start, end;
time(&start);
while(a > 1)
{
if(a % i == 0)
{
a /= i;
}
else i++;
}
time(&end);
printf("600851475143的最大质因数为:%d\n", i);
printf("time:%ld\n", end - start);
return 0;
}
这与第七题 类似，只做稍微修改即可得出答案 :6857
int calculatePrime(long long value)
{
int array = {0};
array = 2;
int i = 1;
int j = 3;
int k = 0;
int yes = 1;
while(true)
{
if(array >= value)
{
break;
}
else
{
k = 0;
while( k < i)
{
if(j % array == 0)
{
yes = 0;
break;
}
k++;
}
if(yes && value % j == 0)
{
value /= j;
array = j;
}
}
j++;
yes = 1;
}
return array;
}
int main(int argc, char *argv[])
{
int sum = calculatePrime(600851475143);
printf("%d\n",sum);
return 0;
}
本帖最后由 永恒的蓝色梦想 于 2020-8-21 21:57 编辑
C++ 0ms#include<iostream>
#include<cmath>
#include<cstdint>
using namespace std;
uint64_t maxPrimeDivisor(uint64_t num) {
if (num < 2) {
return 0;
}
while (!(num & 1)) {
num >>= 1;
}
if (num != 1) {
uint64_t divisor = 3, max = sqrt(num);
while (divisor <= max) {
if (num % divisor) {
divisor += 2;
}
else {
do {
num /= divisor;
} while (!(num % divisor));
if (num == 1) {
return divisor;
}
max = sqrt(num);
}
}
return num;
}
return 2;
}
int main() {
ios::sync_with_stdio(false);
cout << maxPrimeDivisor(600851475143) << endl;
return 0;
}
本帖最后由 leon0149 于 2020-5-7 20:44 编辑
71 839 1471 6857
0.002s#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define NUM 600851475143 // 常量定义
int isPrime(int x){
/*
* 判断是不是素数
*/
int ret = 1;
for (int i = 3; i < sqrt(x); i+=2) {
if (x % i == 0)
ret = 0;
}
return ret;
}
int isPrimeLong(long long x){
/*
* 判断是不是素数
*/
int ret = 1;
long double sqr = sqrt(x);
for (long i = 3; i < sqr; i+=2) {
if (x % i == 0)
ret = 0;
}
return ret;
}
int main(void)
{
int *array = NULL;
long long *array2 = NULL;
double sqr = sqrt(NUM);
int cnt = 0;
int cnt2 = 0;
for (int i = 3; i < sqr; i+=2) {
/*
* 把这个数据分成两部分
*/
if (NUM % i == 0){
/*
* 判断能不能被这个数据整除
*/
if (isPrime(i)){
/*
* 判断是不是素数
* 如果是
* 那么分配一个数据的内存
* 把这个素数放到数组array里面
*/
array = (int *)realloc(array, sizeof(int));
array = i;
cnt++;
}
long long num = NUM / i; // 如果上面i可以被整除那么 一定有另一个数匹配这个i
if (isPrimeLong(num)){
/*
* 判断这个另一个数是否是素数
* 如果是 那么分配一个数据的内存
* 因为数据可能比较大 所以用long long类型储存
* 把这个数放入long long 类型的数组array2里面
*/
array2 = (long long *)realloc(array2, sizeof(long long));
array2 = i;
cnt2++;
}
}
}
/*
* 分别遍历两个数组
*/
for (int i = 0; i < cnt; ++i) {
printf("%d ", array);
}
for (int i = 0; i < cnt2; ++i) {
printf("%lld ", array2);
}
free(array); // 释放内存
free(array2);
return 0;
}
cupbbboom 发表于 2018-11-15 16:46
有没有跟我一样：先百度合数 、质数因子，然后就有了百度什么是质数？什么是因数？什么是整数、正整数? ...
这是小学的知识
guoquanli 发表于 2019-12-31 14:56
非常感谢您的分享，请教您一下，我在linux环境下运行您的这段代码提示：unknowntypename '__int64', ...
把 __int64 改成 long long