Matlab - trenger litt innsikt

[hifiking]

Jeg har forsøkt å lage en funksjon som sjekker for primtall.

Har prøvd å bruke "Miller–Rabin primality test", men i tillegg til ikke å være helt stødig i matlab er jeg heller ikke helt sikker på selve matten.

 

Funksjonen finner primtall, men ikke alle. Feks 31 finner den ikke. Den skal i utgangspunktet finne alle primtallene, og noen som ikke er primtall med en feilmargin på 4^-k.

 

http://en.wikipedia...._primality_test

 

Hvorfor finner den ikke 31. Jeg tror noe av grunnen kan være mitt lavpannede forsøk på "%write n - 1 as 2^s * d with d odd by factoring powers of 2 from n - 1".

 

function [ out ] = prime( n )
%PRIME Summary of this function goes here
%   Detailed explanation goes here
%Input: n > 3, an odd integer to be tested for primality;
%Input: k, a parameter that determines the accuracy of the test
%Output: composite if n is composite, otherwise probably prime
%write n - 1 as 2^s * d with d odd by factoring powers of 2 from n - 1
%LOOP: repeat k times:
%   pick a random integer a in the range [2, n - 2]
%   x <- a^d mod n
%   if x = 1 or x = n - 1 then do next LOOP
%   for r = 1 .. s
%	  x <- x^2 mod n
%	  if x = 1 then return composite
%	  if x = n - 1 then do next LOOP
%   return composite
%return probably prime
n=31;
if n < 4;
out = 0;
return;
end
if mod(n,2) == 0
 out = 0;
 return;
end
s = 0;
d = (n-1)/(2.^(s));
while mod(d,2) == 0
	s = s+1;
	d = (n-1)/(2.^(s));
end

fd = floor(d);
while fd ~= d;
s = s + 1;
d = (n-1)/(2.^(s));
fd = floor(d);
end

k = 10;
t1 = 0;
while t1 < k
l=0;
a = randi((n-2),1,1);
x = mod((a.^d),n);
if x == 1
t1 = t1+1;
continue;
end
if x == (n-1)
t1 = t1+1;
continue;
end
for r = 1:s
x = mod((x.^2),n);
if x == 1
	out = 0;
end
if x == (n-1)
	t1 = t1 + 1;
	l=1;
	break;
end
end
if l == 1;
continue;
end
out = 0;
return;
end
out = 1;
return;
end

[Foxboron]

Kan det hende at dette hjelper deg?

Skudd i mørket tho.

 

def isPrime(n):
   if n < 2:
    return False
   if n == 2:
    return True
   if not n & 1:
    return False
   for i in range(3, int(n ** 0.5) + 1, 2):
    if n % i == 0:
	    return False
   return True

[GeirGrusom]

Er det ikke en debugger i Matlab? Kan du ikke bare kjøre primtesten din på 31 og se hvorfor den ikke passerer testen?

 

http://www.mathworks.se/help/techdoc/matlab_env/brqxeeu-175.html

[Pozzolan]

Har hatt en øving hvor vi hadde i oppgave å lage en slik funksjon, her er i alle fall min kode:

%Oppgave 3
function prime = primtall(tall)
% primtall(5)
if tall < 1
   disp('Tallet er mindre enn 1 og kan derfor ikke være et primtall')
elseif tall == 2
   prime = true;
else
   for i = 2:(tall-1)
    if mod(tall,i) == 0
	    prime = false;
	   break
    else
	    prime = true;
    end
   end
end
end

 

Håper den hjelper noe, i tillegg har du den innebygde funksjonen isprime(x)