Script doesn't seem to be execute properly

5 次查看（过去 30 天）
Manuel Barros
Manuel Barros 2018-12-7
评论： Manuel Barros 2018-12-10
I was hoping to acquire some help on how to make my program work efficiently and not take a substantial amount of time to finish:
clear variables
a=...;
p=nextprime(a);
count=0;
limit=200000;
tic
while isprime((p-1)/2)~=1
a=a+1;
p=nextprime(a);
count=count + 1;
if count>limit
break
end
end
toc
This program outputs a number p greater than a such that p is prime and (p-1)/2 is prime. However I've noticed that for any number a greater than approximately 15 digits, the program will take an absurd amount of time to finish, which isn't ideal since I need to test numbers of the order 10^50.

请先登录，再回答此问题。

采纳的回答

Walter Roberson
Walter Roberson 2018-12-7
Beyond about 4E15 the distance between adjacent representable doubles becomes greater than 1. p becomes forced to be even (and so not a prime) and p-1 becomes the same as p .
You can do marginally better by switching to uint64, which gets you to about 1.8E19 . But you cannot get beyond that using ordinary numeric forms.
You need to switch to a variable precision toolbox, such as Symbolic Toolbox, or John D'Errico's File Exchange contribution for variable precision integers.
  4 个评论
显示 2更早的评论
Manuel Barros
Manuel Barros 2018-12-8
It is to find the first prime greater than a such that (p-1)/2 is also prime
Walter Roberson
Walter Roberson 2018-12-8
Then it is going to depend upon the quality of implementation of isprime() or nextprime() . There is a possibility that it might be faster to test
test_vals = p : 2 : p + 10000;
candidate_mask = isprime(test_vals);
next_few_primes = test_vals(candidate_mask);
instead of looping doing nextprime().
But that is going to depend on how the isprime() and nextprime() are implemented in the symbolic package.

请先登录，再进行评论。

更多回答（1 个）

Christopher Creutzig
编辑：Christopher Creutzig 2018-12-10
In your code, you spend a lot of time computing the same prime over and over again. Do not start the search at a+1 for the second search, but start after the prime you already found.
It might also be marginally faster to look for the next prime q starting at a/2 such that p=2*q+1 is also prime.
>> tic
>> a = sym('12345678901234567890');
>> q = nextprime(fix(a/2));
>> while ~isprime(2*q+1), q = nextprime(q+1); end
>> toc
Elapsed time is 4.304840 seconds.
>> [q, 2*q+1]
ans =
[ 6172839450617290091, 12345678901234580183]
  2 个评论
Manuel Barros
Manuel Barros 2018-12-10
Yes thank you, I happened to notice this underlying issue a while after. :)

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Number Theory 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by