-3

This is the code I know:

bool checkPrime(int n) {
    bool prime = true;

    for (int i = 2; i < n; i++) {
        if ((n%i) == 0) {
            prime = false;
        }
    }
    return prime;
}

But is this ok if you’re looking for prime numbers:

List<int> arr = [2, 3, 5, 7]; // Already known

int n = 30; // Between 1 to 30. It could be any number

for (int i = 2; i < n; i++) {
    if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0) {
        arr.add(i);
    }
    // Then maybe some code for numbers less than 8
}

print(arr);

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

And also is there much difference in time complexity?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Random Stuff
  • 37
  • 3
  • because the last one is efficient and it's fast. – Jitu DeRaps Oct 20 '21 at 04:58
  • 2
    The first example takes more time than it needs to. You can `return false;` as soon as `n % i == 0`. At the end of the function you can safely `return true;` if you've made it through the loop. There are other optimizations, but this is the easiest. – Chris Oct 20 '21 at 04:59
  • Thanks for your answers: I came up with the second code but wasn't sure if it was efficient and also am sure someone else has thought of this not just me but wasn't sure as well – Random Stuff Oct 20 '21 at 05:04
  • 2
    As a general rule you should never write a `checkPrime()` method of this form. You should use the Sieve of Eratosthenes plus improvements to generate the primes in the range you're interested in, and then do a table lookup for each check. – user207421 Oct 20 '21 at 05:44
  • @user207421 thanks I didn’t know about this Sieve of Eratosthenes I will check it up – Random Stuff Oct 20 '21 at 05:51
  • Same question was asked yesterday, but today includes answer from yesterday. – brian beuning Oct 22 '21 at 11:51

1 Answers1

1

Your code is incorrect. This code only works because you are taking the value of n as 30, for a greater number like 1000 this will produce an incorrect result. List arr = [2,3,5,7]; // already known

int n = 1000; // between 1 to 1000 it could be any number
List<int> arr = [2,3,5,7];

for (int i = 2; i < n; i++) {
    if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0){
        arr.add(i);
    }
    //Then maybe some code for numbers less than 8
}
  
print(arr);

Your code will return 231 prime numbers when there are actually only 168 prime numbers. This is because you are not considering the future prime numbers that can only be divided by a prime number between 7 to that number.

eg: 121 will be returned by you as prime but it is a multiple of 11

Extending your pattern. Though this will be faster since it has reduced a number of division operations but due to two loops, it will still be N square.

Here I am simply only dividing numbers from the existing prime numbers collection and adding them in the collection if prime is found tobe used in next iteration for division.

  List < int > arr = [2]; // taking 2 since this is the lowerst value we want to start with 
    
    int n = 30; // n can between 2 to any number
    if (n < 3) {
    
        print(arr); // can return from here.
    }
    // since we already have added 2 in the list we start with next number to check that is 3
    for (int i = 3; i < n; i++) {
        bool isPrime = true;
        for (int j = 0; j < arr.length; j++) { // we iterate over the current prime number collection only [2] then [2,3]...
            if (i % arr[j] == 0) { // check if number can be divided by exisiting numbers
                isPrime = false;
            }
        }
    
        if (isPrime) { // eg: 2 cant divide 3 so we 3 is also added 
            arr.add(i)
        }
    
    }
    
    print(arr);

You can look a faster pattern here. Which is the fastest algorithm to find prime numbers?

vaira
  • 2,191
  • 1
  • 10
  • 15