Body: <p>I have started studying ML just a short while ago, so that my questions will be very elementary. That being so, if they are not welcome, just tell me and I'll stop asking them.</p>
  <p>I gave myself a homework project which is to make an ML algorithm be able to learn that, if the last digit of a number <span class="math-container">$n$</span> is <span class="math-container">$0, 2, 4, 5, 6$</span> or <span class="math-container">$8$</span>, then it cannot be a prime, provided <span class="math-container">$n &gt; 5$</span>. Note that, if a number <span class="math-container">$n$</span> ends with <span class="math-container">$0, 2, 4, 6, 8$</span>, then it is even, so it is divisible by <span class="math-container">$2$</span>, hence not prime. Similarly, numbers ending in <span class="math-container">$5$</span> are divisible by <span class="math-container">$5$</span>, so they cannot be prime.</p>
  <p>Which ML approach should I choose to solve this problem? I know that I don't need ML to solve this problem, but I am just trying to understand which ML approach I could use to solve this problem.</p>
  <p>So far, I have only learned about two ML approaches, namely linear regression (LR) and <span class="math-container">$k$</span>-nearest neighborhoods, but they both seem inappropriate in this case since LR seems to be a good choice in finding numerical relations between input and output data and KNN seems to be good at finding clusters, and &quot;primality&quot; has neither of these characteristics.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-14T08:42:22.090Z
Comments.Text: Your homework project is more suited to use [neural networks](https://ai.stackexchange.com/questions/15594/what-are-all-the-different-kinds-of-neural-networks-used-for). You might find it easier to approach that problem when you have some knowledge about them. But even then, for this particular task, you might not get the results you currently have in mind. See this related question: https://ai.stackexchange.com/questions/3389/could-a-neural-network-detect-primes
Comments.UserDisplayName: mugoh
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-14T18:47:51.987Z
Comments.Text: Ok, have you already tried to build the labeled dataset? Of course, you can build this easily. Now, the first problem is deciding whether this should be a classification or regression problem. Given that the output of the ML model should either be "prime" or "not prime", then this is a categorical/nominal output/dependent variable, hence this is a classification problem, specifically, a binary classification problem. You can **try to** use any ML method that is able to perform classification. Another problem is how to represent the inputs.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-14T18:50:43.967Z
Comments.Text: @nbro I have made a labeled dataset with the numbers 1-10000. Thanks for the answer. I'll look for classification algorithms tomorrow (day off today). If you know a good source of interesting ML exercises to practice and learn, i'd appreciate them
Comments.UserDisplayName: Vni Versvs
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-14T18:52:23.977Z
Comments.Text: Anyway, in principle, you can just pass the last digit of the input numbers to the neural network (of course, this assumes that you exclude all numbers between $0$ and $5$ when passing them to the network). The neural network will just need to determine whether the numbers are even or $5$, so essentially we have $10$ digits, and $6$ of them will need to be memorised and mapped to one class, and the other $4$ will need to be mapped to another class.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-14T18:54:00.053Z
Comments.Text: @nbro, yes, it does seem like NN are the way to go, as also mugoh pointed out.
Comments.UserDisplayName: Vni Versvs
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-14T18:54:42.497Z
Comments.Text: @VniVersvs Oh, not necessarily. I just said "network" but I actually meant any ML model that performs classification and accepts different types of inputs.
Comments.UserDisplayName: nbro
Tags: <machine-learning><classification><homework><primality-test>
Title: Which ML approach could determine that a number greater than 5 is not prime, knowing that a number is not prime if it ends with an even digit or 5?
UserDisplayName: Vni Versvs
ThreadText: # Which ML approach could determine that a number greater than 5 is not prime, knowing that a number is not prime if it ends with an even digit or 5?
  
  (Asked by: username_0 on 2020-11-13)
  
  I have started studying ML just a short while ago, so that my questions will be very elementary. That being so, if they are not welcome, just tell me and I'll stop asking them.
  
  I gave myself a homework project which is to make an ML algorithm be able to learn that, if the last digit of a number $n$ is $0, 2, 4, 5, 6$ or $8$, then it cannot be a prime, provided $n > 5$. Note that, if a number $n$ ends with $0, 2, 4, 6, 8$, then it is even, so it is divisible by $2$, hence not prime. Similarly, numbers ending in $5$ are divisible by $5$, so they cannot be prime.
  
  Which ML approach should I choose to solve this problem? I know that I don't need ML to solve this problem, but I am just trying to understand which ML approach I could use to solve this problem.
  
  So far, I have only learned about two ML approaches, namely linear regression (LR) and $k$-nearest neighborhoods, but they both seem inappropriate in this case since LR seems to be a good choice in finding numerical relations between input and output data and KNN seems to be good at finding clusters, and "primality" has neither of these characteristics.
  
  **Tags:** machine-learning, classification, homework, primality-test
  > **Comments:**
  > **username_1**: Your homework project is more suited to use [neural networks](https://ai.stackexchange.com/questions/15594/what-are-all-the-different-kinds-of-neural-networks-used-for). You might find it easier to approach that problem when you have some knowledge about them. But even then, for this particular task, you might not get the results you currently have in mind. See this related question: https://ai.stackexchange.com/questions/3389/could-a-neural-network-detect-primes  
  > **username_2**: Ok, have you already tried to build the labeled dataset? Of course, you can build this easily. Now, the first problem is deciding whether this should be a classification or regression problem. Given that the output of the ML model should either be "prime" or "not prime", then this is a categorical/nominal output/dependent variable, hence this is a classification problem, specifically, a binary classification problem. You can **try to** use any ML method that is able to perform classification. Another problem is how to represent the inputs.  
  > **username_0**: @nbro I have made a labeled dataset with the numbers 1-10000. Thanks for the answer. I'll look for classification algorithms tomorrow (day off today). If you know a good source of interesting ML exercises to practice and learn, i'd appreciate them  
  > **username_2**: Anyway, in principle, you can just pass the last digit of the input numbers to the neural network (of course, this assumes that you exclude all numbers between $0$ and $5$ when passing them to the network). The neural network will just need to determine whether the numbers are even or $5$, so essentially we have $10$ digits, and $6$ of them will need to be memorised and mapped to one class, and the other $4$ will need to be mapped to another class.  
  > **username_0**: @nbro, yes, it does seem like NN are the way to go, as also mugoh pointed out.  
  > **username_2**: @VniVersvs Oh, not necessarily. I just said "network" but I actually meant any ML model that performs classification and accepts different types of inputs.  
  
  ---
  
  ## 0 answers
  
  