1

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.

nbro
  • 39,006
  • 12
  • 98
  • 176
Vni Versvs
  • 11
  • 1
  • 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 – mugoh Nov 14 '20 at 08:42
  • 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. – nbro Nov 14 '20 at 18:47
  • @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 – Vni Versvs Nov 14 '20 at 18:50
  • 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. – nbro Nov 14 '20 at 18:52
  • @nbro, yes, it does seem like NN are the way to go, as also mugoh pointed out. – Vni Versvs Nov 14 '20 at 18:54
  • 1
    @VniVersvs Oh, not necessarily. I just said "network" but I actually meant any ML model that performs classification and accepts different types of inputs. – nbro Nov 14 '20 at 18:54

0 Answers0