So, you have fallen love at the very first sight! And, thank god, it is not one of those imbecile apes. It is rather a species from a completely different kingdom- Machinia.
Write a program that tells if an integer is prime or not.
01. Base Programmer
Though you knew how prime numbers work, it took a long time to come up with this logic. Also, You made several mistakes on the way. But now, you are proud of your brilliant solution.
int func(int a)
{
int x,i, r;
x = 0;
i = 0 ;
for(i=1; i<=a ; i=i+1 )
{
if(a%i == 0)
{x=x+1 ;}
}
if( x == 2)
{r = 1;}
else
{r = 0;}
return r ;
}You have learned to use flags, and think that they are the coolest. Also, indentation is super important!
int pri_num(int a) {
int i = 0, f = 0;
for (i = 2; i < a; i ++)
if (a % i == 0) f = 1;
if (f == 0) return 1;
else return 0;
}You don't need to calculate all the way to the end; finding one divisor is enough. So, just return; no need for 'flag'. break would do too, but return is better.
int prime_num(int x){
int i = 2;
while (i < x){
if (x % i == 0){
return 0;
}
i++;
}
return 1;
}You have grown SMARTER and have halved the run time by checking divisibility with odd-numbers only. You also understand that looping till 'x/2' is enough.
int prime_or_not(int x) {
if (x == 2) {
return 1;
}
if (x % 2 == 0) {
return 0;
}
int i;
for (i = 3; i < x/2; i += 2) {
if (x % i == 0){
return 0;
}
}
return 1;
}You want everyone to understand your code easily. So, you put some REALLLLY helpful comments. Runtime is cut from 'n/2' to 'n/3'.
/*
* checks if a number is prime
*/
int prime_check(int n){
if (n == 2){ // 2 is prime
return 1;
}
if (n % 2 == 0){ // if divisible by 2 then not prime
return 0;
}
int i = 3; // i is odd
int lim = n/3;
for (; i < lim; i += 2){ // check for all odd numbers till n/3
if (n % i == 0){ // if divisible then not prime
return 0; // not prime
}
}
return 1; // is prime number
}Now, you understand- mere comment cannot make bad code look good. So, you get rid of those crappy names and annoying comments. And now, the code is truly readable.
bool primeNumberChecker(int number){
if (number == 2){
return true;
}
if (number % 2 == 0){
return false;
}
int limit = number/3;
for (int factor = 3; factor < limit; factor += 2){
if (number % factor == 0){
return false;
}
}
return true;
}07. Super Programmer
You have improved time complexity from 'n' to '√n'! BRILLIANT!!!
You covered boundary cases too: no room for unreliable codes :)
Most importantly, who elite uses the tab?!
#include <math.h>
bool checkPrime(int number) {
if (number < 2) {
return false;
}
if (number == 2) {
return true;
}
if (number % 2 == 0) {
return false;
}
int limit = sqrt(number);
for (int factor = 3; factor <= limit; factor += 2) {
if (number % factor == 0) {
return false;
}
}
return true;
}You have come up with a more clever solution for computing '√n'. In fact, you don't really need to calculate it!
2 == number, instead of number == 2, can save you from lots of troubles caused by mistyping one = by giving a compilation error in place of an undetectable bug.
bool isPrime (int number) {
if (2 == number) {
return true;
}
if (2 > number || 0 == number%2) {
return false;
}
for (int factor = 3; factor*factor <= number; factor += 2) {
if (0 == number%factor) {
return false;
}
}
return true;
}As we don't need to check divisibility by all even numbers after checking by 2, the same goes for 3. So now, we are checking divisibility by only the odd numbers that are not multiples of 3.
bool isPrime (int number) {
if (3 >= number) {
if (2 > number) {
return false;
}
return true;
}
if (0 == (number&1) || 0 == (number%3)) {
return false;
}
int factor = 5;
while (factor*factor <= number) {
if (0 == number%factor) {
return false;
}
factor += 2;
if (0 == number%factor) {
return false;
}
factor += 4;
}
return true;
}You simply got over-bored...
bool isPrime(int N, int _=2){
return _*_>N?1<N:N%_&&isPrime(N,++_);
}u don't give a duck
public class PrimeNumberChecker {
public boolean isPrime(int n) {
return n>1?!new String(new char[n]).matches(".?|(..+?)\\1+"):false;
}
}Execution time is more important than memory consumption. And if you can do some preprocessing, then you should. Thus for smaller integers, you have reduced the complexity from √n to 1.
public class PrimeNumberChecker {
public static final int MAX_MEMORY_SPACE = 64000000;
public static final int MIN_MEMORY_SPACE = 4;
private boolean[] primeNumberMarks;
public PrimeNumberChecker() {
this(MAX_MEMORY_SPACE);
}
public PrimeNumberChecker(int maxValue) {
if (MAX_MEMORY_SPACE < maxValue) {
maxValue = MAX_MEMORY_SPACE;
} else if (MIN_MEMORY_SPACE > maxValue) {
maxValue = MIN_MEMORY_SPACE;
}
this.primeNumberMarks = new boolean[maxValue+1];
markPrimeNumbers();
}
private void markPrimeNumbers() {
for (int i = 2; i < primeNumberMarks.length; ++i) {
primeNumberMarks[i] = true;
}
for (int i = 2; i*i <= primeNumberMarks.length; ++i) {
if (true == primeNumberMarks[i]) {
for (int j = i+i; j < primeNumberMarks.length; j += i) {
primeNumberMarks[j] = false;
}
}
}
return;
}
public boolean isPrime(int number) {
if (number < 0) {
return false;
} else if (number < primeNumberMarks.length) {
return primeNumberMarks[number];
} else {
return checkPrime(number);
}
}
private boolean checkPrime (int number) {
if (0 == (number%2) || 0 == (number%3)) {
return false;
}
int factor = 5;
while (factor*factor <= number) {
if (0 == number%factor) {
return false;
}
factor += 2;
if (0 == number%factor) {
return false;
}
factor += 4;
}
return true;
}
}
ProgrammerTransformation is licensed under MIT License.