Determining if a number is prime without using a for loop

Discussion in 'Homework Help' started by ckuylen, Feb 1, 2012.

  1. ckuylen

    Thread Starter New Member

    Feb 1, 2012
    8
    0
    Hello all. I'm new to this forum and I am amazed at the number and density of topics. I am a beginner to MATLAB and I am trying to learn the basics of matlab so I can code my own experiments. I am having trouble understanding one of our homework problems and thought someone here might be able to help me out.

    Specifically, we are asked to create a function that will determine if a number is prime without using a for loop. In this circumstance your function should be vectorized. I have figured out how to determine if a number is prime with a for loop, but I am unsure how to determine if a number is prime by writing a function using a vector. Any help would be greatly appreciated.

    This is what I have tried already, but I get no results for my output:

    function [noloop]=isPrime_noloop(n)
    n = ones(1,40000000);
    j = 2;
    while(j<(40000000/2))
    n((j*2):j:end) = 0;
    j = j+1;
    while(n(j)==0) % find next prime
    j = j+1; end
    end

    As I said, I am not sure if I am on the right path or not, this is all new to me. I appreciate any and all responses.

    Cheers!
     
  2. hgmjr

    Moderator

    Jan 28, 2005
    9,030
    214
    If this is a homework problem then I need to move it to the homework section of the forum.

    Here at AAC, we prefer that students show their efforts to solve a problem on their own. You have done that nicely.

    Our member are here to assist you with hints and suggestions. Someone with MATLAB experience should be along shortly to assist you,

    Good luck,
    hgmjr
     
  3. ckuylen

    Thread Starter New Member

    Feb 1, 2012
    8
    0
    Well thank you super mod for filling me in. I tweaked this a little and it spits out columns from 1-40000000 and tells me where in these columns a prime number is located. This is not what I want!! I want to determine if a number that I select is prime using a vector (i.e. all I want to do is type in a value, lets say 37 and have matlab spit out a 1 or 0 to tell me if this number is prime).

    Here is the tweaked version of the original code that now returns this massive matrix(?) of 1s and 0s.

    function z = isPrime_noloop(x)
    z = ones(1,40000000);
    j = 2;
    while(j<(40000000/2))
    z((j*2):j:end) = 0;
    j = j+1;
    while(z(j)==0) % find next prime
    j = j+1; end
    end
     
  4. t_n_k

    AAC Fanatic!

    Mar 6, 2009
    5,448
    782
    Are you allowed to use the Matlab inbuilt "primes()" function?

    If so you could have something like

    Code ( (Unknown Language)):
    1. [COLOR=#000000]
    2. x[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#AE5CB0][U]input[/U][/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#BC8F8F]Enter value to check if prime: [/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#4A55DB])[/COLOR] [COLOR=#000000]
    3. y[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#AE5CB0][U]primes[/U][/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]x[/COLOR][COLOR=#4A55DB])[/COLOR] [COLOR=#000000]
    4. s[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#32B9B9]size[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]y[/COLOR][COLOR=#4A55DB])[/COLOR] [COLOR=#A020F0]
    5. if[/COLOR] [COLOR=#000000]y[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]s[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#BC8F8F]2[/COLOR][COLOR=#4A55DB])[/COLOR][COLOR=#4A55DB])[/COLOR][COLOR=#5C5C5C]==[/COLOR][COLOR=#000000]x[/COLOR] [COLOR=#A020F0]then[/COLOR] [COLOR=#000000]result[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#BC8F8F]T[/COLOR][COLOR=#BC8F8F]"[/COLOR] [COLOR=#A020F0]
    6. else[/COLOR] [COLOR=#000000]result[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#BC8F8F]F[/COLOR][COLOR=#BC8F8F]"[/COLOR]    
    7. [COLOR=#A020F0]end[/COLOR]
     
    Last edited: Feb 2, 2012
  5. t_n_k

    AAC Fanatic!

    Mar 6, 2009
    5,448
    782
    Or more simply ....

    Code ( (Unknown Language)):
    1.  
    2. [COLOR=#000000]x[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#AE5CB0][U]input[/U][/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#BC8F8F]Enter value to check if prime: [/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#4A55DB])[/COLOR]
    3. [COLOR=#000000]y[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#AE5CB0][U]primes[/U][/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]x[/COLOR][COLOR=#4A55DB])[/COLOR] [COLOR=#A020F0]
    4. if[/COLOR] [COLOR=#32B9B9]max[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]y[/COLOR][COLOR=#4A55DB])[/COLOR][COLOR=#5C5C5C]==[/COLOR][COLOR=#000000]x[/COLOR] [COLOR=#A020F0]then[/COLOR] [COLOR=#000000]result[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#BC8F8F]T[/COLOR][COLOR=#BC8F8F]"[/COLOR] [COLOR=#A020F0]
    5. else[/COLOR] [COLOR=#000000]result[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#BC8F8F]F[/COLOR][COLOR=#BC8F8F]"[/COLOR]
    6. [COLOR=#A020F0]end[/COLOR]
    7.  
     
    ckuylen likes this.
  6. ckuylen

    Thread Starter New Member

    Feb 1, 2012
    8
    0
    Well the instructions just said to use a vector without using a forloop so maybe this will work. I'll shoot him an email and see what he says. Thanks for your input.
     
  7. ckuylen

    Thread Starter New Member

    Feb 1, 2012
    8
    0
    Well primes is out of the question, it is too easy or so I'm told :).

    Here is what I have done now which gives me the correct answer:

    function [y]=isPrime_noloop(x)
    z=[2:x-1];
    if x./z==x
    x=1
    else x=0
    end
    end

    The only question remaining is when I divide x by the numbers in z, what tells meif x isprime? Is it that the quotient is equal to x (like I wrote)?

    Any help on this last point would be greatly appreciated.
     
  8. t_n_k

    AAC Fanatic!

    Mar 6, 2009
    5,448
    782
    I've not convinced myself your code works - as shown.

    I would do something like this for the code body as a command window script. Result = 'T' indicates the entered no. is prime.

    Code ( (Unknown Language)):
    1.  
    2. [COLOR=#000000]x[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#AE5CB0][U]input[/U][/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#BC8F8F]Enter number to test if prime:[/COLOR][COLOR=#BC8F8F]"[/COLOR][COLOR=#4A55DB])[/COLOR]
    3. [COLOR=#000000]z[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#4A55DB][[/COLOR][COLOR=#BC8F8F]2[/COLOR][COLOR=#FFAA00]:[/COLOR][COLOR=#000000]x[/COLOR][COLOR=#5C5C5C]-[/COLOR][COLOR=#BC8F8F]1[/COLOR][COLOR=#4A55DB]][/COLOR]
    4. [COLOR=#000000]A[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#000000]x[/COLOR][COLOR=#5C5C5C]./[/COLOR][COLOR=#000000]z[/COLOR]
    5. [COLOR=#000000]B[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#000000]A[/COLOR][COLOR=#5C5C5C]-[/COLOR][COLOR=#32B9B9]int[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]A[/COLOR][COLOR=#4A55DB])[/COLOR]
    6. [COLOR=#A020F0]if[/COLOR] [COLOR=#32B9B9]nnz[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]B[/COLOR][COLOR=#4A55DB])[/COLOR][COLOR=#5C5C5C]==[/COLOR][COLOR=#32B9B9]nnz[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]A[/COLOR][COLOR=#4A55DB])[/COLOR] [COLOR=#A020F0]then[/COLOR] [COLOR=#000000]result[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]'[/COLOR][COLOR=#BC8F8F]T[/COLOR][COLOR=#BC8F8F]'[/COLOR]
    7. [COLOR=#A020F0]else[/COLOR] [COLOR=#000000]result[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]'[/COLOR][COLOR=#BC8F8F]F[/COLOR][COLOR=#BC8F8F]'[/COLOR] [COLOR=#A020F0]
    8. end[/COLOR]
    9.  
     
  9. stahta01

    Member

    Jun 9, 2011
    133
    21
    In C, when not using loop is a requirement it often means using recursion instead.
    Does, Matlab do recursion?
    If yes, you might ask if that is needed in the answer.

    I have no idea how using recursion can solve your problem.

    Tim S.
     
  10. ckuylen

    Thread Starter New Member

    Feb 1, 2012
    8
    0
    Well this is due in a few hours, so I'm not sure if anyone will get to it on time. I appreciate all of the advice so far and as I said I'm new so this is like trying to learn Mandarin for me.

    Anyway this is what I have done now:
    function [noloop]=isPrime_noloop(R)
    %Determines if a number is prime without using a for loop
    %Syntax: out=isPrime_noloop(x);
    %Import: x=integer to check;
    %Export: [noloop]=0 if not prime, 1 if prime
    %
    %My Name
    %February 3 2012
    Integer=y==round(y);
    Vector=[2:R-1];
    Divisor=R./vector;
    Check=Divisor-Integer(Divisor);
    if nnz(Check)==nnz(divisor)
    [noloop]=1;
    else [noloop]=0;
    end

    **Now instead of returning a 1 or a zero to tell me if a single answer is prime. It checks all values between 2 and 1 less than my input and returns something like this in the command window:
    >> isPrime_noloop(47)

    ans =

    Columns 1 through 21
    23 15 11 9 7 6 5 5 4 4 3 3 3 3 2 2 2 2 2 2 2

    Columns 22 through 42
    2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

    Columns 43 through 45

    1 1 1

    **Although all I need is for it to tell me is if 47 is prime than all I should get for my output is a 1, but if it is not prime all I should get for my output is 0. I am unsure where all of these other values are coming from.

    Again thank you all for your time and patience.
     
  11. t_n_k

    AAC Fanatic!

    Mar 6, 2009
    5,448
    782
    Disregarding all the trimmings the core code lines below worked fine for me.

    My Matlab clone [Scilab] uses int() for integer operation but round() also works OK. Why did you define the function Integer instead of just using the inbuilt round()?

    You may need to watch your variable names if they are case sensitive in Matlab. You've used both upper and lower case for the same variable Vector / vector.

    Code ( (Unknown Language)):
    1.  
    2. [COLOR=#B01813]function[/COLOR] [COLOR=#4A55DB][[/COLOR][COLOR=#834310][B]noloop[/B][/COLOR][COLOR=#4A55DB]][/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#000000][U]isPrime_noloop[/U][/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#834310][B]R[/B][/COLOR][COLOR=#4A55DB])[/COLOR] [COLOR=#000000]
    3. Vector[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#4A55DB][[/COLOR][COLOR=#BC8F8F]2[/COLOR][COLOR=#FFAA00]:[/COLOR][COLOR=#834310][B]R[/B][/COLOR][COLOR=#5C5C5C]-[/COLOR][COLOR=#BC8F8F]1[/COLOR][COLOR=#4A55DB]][/COLOR][COLOR=#000000];[/COLOR] [COLOR=#000000]
    4. Divisor[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#834310][B]R[/B][/COLOR][COLOR=#5C5C5C]./[/COLOR][COLOR=#000000]Vector[/COLOR][COLOR=#000000];[/COLOR] [COLOR=#000000]
    5. Check[/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#000000]Divisor[/COLOR][COLOR=#5C5C5C]-[/COLOR][COLOR=#32B9B9]round[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]Divisor[/COLOR][COLOR=#4A55DB])[/COLOR][COLOR=#000000];[/COLOR]
    6. [COLOR=#A020F0]if[/COLOR] [COLOR=#32B9B9]nnz[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]Check[/COLOR][COLOR=#4A55DB])[/COLOR][COLOR=#5C5C5C]==[/COLOR][COLOR=#32B9B9]nnz[/COLOR][COLOR=#4A55DB]([/COLOR][COLOR=#000000]Divisor[/COLOR][COLOR=#4A55DB])[/COLOR] [COLOR=#4A55DB][[/COLOR][COLOR=#834310][B]noloop[/B][/COLOR][COLOR=#4A55DB]][/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]1[/COLOR][COLOR=#000000];[/COLOR] [COLOR=#A020F0]
    7. else[/COLOR] [COLOR=#4A55DB][[/COLOR][COLOR=#834310][B]noloop[/B][/COLOR][COLOR=#4A55DB]][/COLOR][COLOR=#5C5C5C]=[/COLOR][COLOR=#BC8F8F]0[/COLOR][COLOR=#000000];[/COLOR] [COLOR=#A020F0]
    8. end[/COLOR] [COLOR=#B01813]
    9. end[/COLOR]
    10.  
     
    ckuylen likes this.
  12. t_n_k

    AAC Fanatic!

    Mar 6, 2009
    5,448
    782
    Matlab fix() seems to have the same functionality as that of my earlier use of int() in Scilab ...
     
  13. ckuylen

    Thread Starter New Member

    Feb 1, 2012
    8
    0
    Thank you so much. Your a lifesaver, now I can move onto scripts and cell arrays and I have a feeling I will be back. I came so close a couple of times to cracking this on my own; either way it feels great now.

    I defined the function integer because that was one of the first assignments in class, but using the built in round function is much easier.

    I need a smiley that is drinking a beer or a pop (if thats your thing) I owe you one!
     
Loading...