My loop is not so infinite?

This is a discussion on My loop is not so infinite? within the C++ Programming forums, part of the General Programming Boards category; the original way will not accurately determine if a number is prime, it will only determine if a number is ...

  1. #16
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    the original way will not accurately determine if a number is prime, it will only determine if a number is odd, not all odd numbers are prime ( 9 and 15 for example). The method I posted will absolutely determine if its prime or not. Although the method I gave you is probably the slowest 'fast' method there is, its also the simplest. There are far faster methods otu there, but the maths gets thick.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  2. #17
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,635
    Quote Originally Posted by Caduceus View Post
    Aha! I never thought of using logical-or! I tried to implement a break if the user enters zero, but that didn't work :P Sorry to keep asking questions, but I've read the short tutorial, and I can't figure it out, how does break work?
    Though you may not need break here, a break keyword simple aborts a loop, the loop it is written in:
    Code:
    int main()
    {
    	for (int i = 0; i < 100000; i++)
    	{
    		if (i == 100) break;
    	}
    	return 0;
    }
    When i hits 100, the loop aborts due to the break keyword.

    Quote Originally Posted by abachler View Post
    Personally I woudl do this ---
    What's with the poor indentation?
    Perhaps you need to read
    http://cpwiki.sf.net/Indentation
    Last edited by Elysia; 01-26-2008 at 11:38 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #18
    Beginner in C++
    Join Date
    Dec 2007
    Posts
    34
    Elysia, I did it like that but it wouldn't work. It didn't give me any errors, it just wouldn't abort when I entered 0.

  4. #19
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,635
    The use of a loop in your code is not needed. I just demonstrated how the keyword break works.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #20
    Beginner in C++
    Join Date
    Dec 2007
    Posts
    34
    I mean I used it in one of the first drafts of the program. I'll keep experimenting and see what I can come up with.

    Thanks for the information you all have given

  6. #21
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    If abachler's code confused you a little, here it is a little simpler. It will take a bit longer to run though.
    Code:
    #include <iostream>
    using namespace std;
     
    // Prime number function - Tests number for remainder. If none is found, return false. Otherwise, return true.
     
    bool PrimeFunction()
    {
        int n;
     
        cin >> n;
        cin.ignore();
     
        for (int i = 2; i < n; i++)
        {
            if (n%i == 0)
            {
                cout << "Number is not prime";
                return false;
            }
        } 
        cout << "Number is prime";
        return true;
    }
    The code works by testing every factor of a number to see if it has no remainder, and if one such number evenly divides "n," n cannot be prime. You could replace "i < n" with "i * i < n", because you only need to test the factors up to the square root of n. If a factor of n is greater than the square root of n, then its corresponding factor is less than "n" so you would have found it anyways. IE, if n = 15, then you wouldn't need to test the factor "5" because the factor "3" would have been tested already.
    Programming Your Mom. http://www.dandongs.com/

  7. #22
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Quote Originally Posted by abachler View Post
    the original way will not accurately determine if a number is prime, it will only determine if a number is odd, not all odd numbers are prime ( 9 and 15 for example). The method I posted will absolutely determine if its prime or not. Although the method I gave you is probably the slowest 'fast' method there is, its also the simplest. There are far faster methods otu there, but the maths gets thick.
    I think he may have been referring to this line:
    Code:
        if (((n/temp)*temp) == n){
    It could be optimised and simplified to this:
    Code:
        if (n % temp == 0){
    Your while loop also involves a multiplication upon each loop, whereas sqrt(n) could be precalculated instead, saving that multiplication.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #23
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    as I said, its probably the slowest 'fast' method out there, not really optimized at all other than to only test factrs less than the sqrt of the number in question. When I said there were faster methods, i wasnt refering to code level optimizations, btu rather algorithms that inherently prove or disprove primality faster. For example, not only will any composite number have a factor less than or equal to its square root, it will have a prime factor less than its square root. The proof is that any non-prime factor can itself be factored into smaler numbers, which will either be prime or can e further factored until some prime number is found. Any factor of a number A is also a factor of some number A * B.

    A much faster method then is to only check the prime numbers less than or equal to sqrt(X). This is the method I used to generate the list of all 32 bit primes. The file doesnt in fact contain the number 2 although 2 is prime. Most algorithms exclude even numbers outright, so this isnt really an issue.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  9. #24
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Actually that's about the slowest implementation of the slowest algorithm.
    For algorithmic improvements you'd need to look into:
    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    and
    http://en.wikipedia.org/wiki/Sieve_of_Atkin
    and more.

    Not meaning to pick on you though. My main point is that it was written in an unnecessarily complicated way as recognised by the OP.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 06-14-2009, 11:24 PM
  2. Cosine fucntion and infinite loop.
    By youareafever in forum C Programming
    Replies: 2
    Last Post: 11-07-2008, 03:45 AM
  3. Infinite Loop with GetAsyncKeyState
    By guitarist809 in forum Windows Programming
    Replies: 1
    Last Post: 04-18-2008, 12:09 PM
  4. Switch statement = infinite loop
    By Lucid003 in forum C++ Programming
    Replies: 10
    Last Post: 10-10-2005, 12:46 AM
  5. stays in loop, but it's not an infinite loop (C++)
    By Berticus in forum C++ Programming
    Replies: 8
    Last Post: 07-19-2005, 11:17 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21