want to know the complexity of my program ,new way to find prime numbers
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: want to know the complexity of my program ,new way to find prime numbers

  1. #1
    Join Date
    Apr 2017
    Posts
    2

    want to know the complexity of my program ,new way to find prime numbers

    Code:
    //simply we are going to use the approach that the numbers that are divisble by prime numbers are not prime and the others are prime.
    #include<stdio.h>
    #include<math.h>
    int main()
    {
    	int n,i,arr[100000],size=0,j,temp;           // array is for storing prime numbers
    	scanf("%d",&n);        // we will be finding prime numbers between 2 to n (both inclusive) 
    	arr[0]=2;              // we know that 2 is a prime number
    	size++;                // we got 1 prime number so size of array gets incremented  
    	for(i=3;i<=n;i++)
    	{
    		temp=pow(i,0.5);       //square root of the number (for which we are going to check is it prime or not)
    		for(j=0;arr[j]<=temp;j++){
    			if(i%arr[j]==0)
    			break;
    		}
    		if(arr[j]>temp)
    		{
    			arr[size]=i;
    			size++;
    		}
    	}
    	for(i=0;i<size;i++)
    	printf("%d \n",arr[i]);
    	return 0;
    }
    Last edited by 2kaud; April 23rd, 2017 at 08:41 AM. Reason: Added code tags

  2. #2
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,956

    Re: want to know the complexity of my program ,new way to find prime numbers

    It would help if you used CODE tags around the code snippets and proper indentations within the code blocks!
    Read also the Announcement: Before you post....: https://eu4.proxysite.com/process.ph...S0qA%3D%3D&b=1
    Victor Nijegorodov

  3. #3
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,956

    Re: want to know the complexity of my program ,new way to find prime numbers

    Sorry! The wrong link address!
    The correct one is http://forums.codeguru.com/announcement.php?f=7
    Victor Nijegorodov

  4. #4
    Join Date
    Apr 2017
    Posts
    2

    Re: want to know the complexity of my program ,new way to find prime numbers

    Quote Originally Posted by VictorN View Post
    Sorry! The wrong link address!
    The correct one is http://forums.codeguru.com/announcement.php?f=7
    sorry but i didn't get what you mean to say ,this is a new problem and i really need the answer .

  5. #5
    Join Date
    Feb 2017
    Posts
    147

    Re: want to know the complexity of my program ,new way to find prime numbers

    Quote Originally Posted by ujjawaltaleja View Post
    this is a new problem and i really need the answer .
    Your algorithm is known as "trial division" (with primes as candidate factors). According to this paper (see page 4 about 10 lines from the bottom),

    https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

    the complexity is Θ(n√n / (log n)^2).
    Last edited by wolle; April 25th, 2017 at 10:39 PM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)