LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 09-02-2012, 01:10 PM   #1
Balvinder87
Member
 
Registered: Jun 2012
Location: India
Distribution: debian
Posts: 77
Blog Entries: 1

Rep: Reputation: Disabled
C fibonacci and prime


In C
A Program That takes a number and checks whether it is prime and also belongs to fibonacci series
 
Old 09-02-2012, 01:46 PM   #2
sag47
Senior Member
 
Registered: Sep 2009
Location: Philly, PA
Distribution: Kubuntu x64, RHEL, Fedora Core, FreeBSD, Windows x64
Posts: 1,506
Blog Entries: 35

Rep: Reputation: 383Reputation: 383Reputation: 383Reputation: 383
Is there a question in there?

Edit: One way you could go about it is first calculate your prime numbers; then calculate your fibonacci sequence which is not less than your highest calculated prime number; and finally create a new list iterating the prime numbers. If the prime number iterated is in the fibonacci sequence list then append it to a new list. Output that new list at the end when all sequences are done.

Last edited by sag47; 09-02-2012 at 04:08 PM.
 
Old 09-02-2012, 02:10 PM   #3
H_TeXMeX_H
Guru
 
Registered: Oct 2005
Location: $RANDOM
Distribution: slackware64
Posts: 12,928
Blog Entries: 2

Rep: Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269
It's probably word for word from the homework assignment.

How about you write the code and see if it runs, if it doesn't then post it and we'll see what is wrong.
 
Old 09-02-2012, 03:47 PM   #4
Balvinder87
Member
 
Registered: Jun 2012
Location: India
Distribution: debian
Posts: 77
Blog Entries: 1

Original Poster
Rep: Reputation: Disabled
My code like this tell me changes
#include<stdio.h>
main()
{
int n, c = 2,k,result;

printf("Enter a number to check if it is prime and fibonacci\n");
scanf("%d",&n);

for ( c = 2 ; c <= n - 1 ; c++ )
{
if ( n%c == 0 )
{
printf("%d is not prime.\n", n);
break;
}
}
if ( c == n )
k=n;
;
fibonacci(k);

return 0;
}


int fibonacci(int n)
{
int a = 0;
int b = 1;
int sum;
int i;
while(sum<n)
{
sum = a + b;
a = b;
b = sum;
if (sum==n)
printf("%d",sum);
}
return 0;
}
 
Old 09-02-2012, 04:06 PM   #5
Snark1994
Senior Member
 
Registered: Sep 2010
Location: Wales, UK
Distribution: Arch
Posts: 1,632
Blog Entries: 3

Rep: Reputation: 345Reputation: 345Reputation: 345Reputation: 345
Use [CODE][/CODE] tags to format your code.

It looks good for the prime checking, the problem is the fibonacci part.

Try something like this (it's your own code with a couple of comments, and cleaned up a whole lot - you'll need to fill in the while loop, we're not doing your homework for you ):

Code:
#include<stdio.h>
int main(){
    int n, c;

    printf("Enter a number to check if it is prime and fibonacci\n");
    scanf("%d",&n);

    for ( c = 2 ; c <= n - 1 ; c++ ){ //not optimal, but simple
        if ( n%c == 0 ){
            printf("%d is not prime.\n", n);
            return 0;
        }
    }
    //so here we know n is prime

    int a = 0;
    int b = 1;
 
    while(a+b <= n){
        //fill in the loop to test if it's fibonacci
    }

    printf("%d is both prime and in the fibonacci sequence",n);
    return 0;
}
You were broadly correct in your first approach, just lots of extra variables and you got a bit confused over the fibonnaci part.

Last edited by Snark1994; 09-02-2012 at 04:08 PM.
 
Old 09-02-2012, 04:06 PM   #6
pixellany
LQ Veteran
 
Registered: Nov 2005
Location: Annapolis, MD
Distribution: Arch/XFCE
Posts: 17,802

Rep: Reputation: 729Reputation: 729Reputation: 729Reputation: 729Reputation: 729Reputation: 729Reputation: 729
Quote:
My code like this tell me changes
please?

Have you tested it?
 
Old 09-02-2012, 04:16 PM   #7
Balvinder87
Member
 
Registered: Jun 2012
Location: India
Distribution: debian
Posts: 77
Blog Entries: 1

Original Poster
Rep: Reputation: Disabled
thanks for wonderful replies got it working now
 
Old 09-02-2012, 05:06 PM   #8
sag47
Senior Member
 
Registered: Sep 2009
Location: Philly, PA
Distribution: Kubuntu x64, RHEL, Fedora Core, FreeBSD, Windows x64
Posts: 1,506
Blog Entries: 35

Rep: Reputation: 383Reputation: 383Reputation: 383Reputation: 383
Since you've got it. Here's a fun example showing the first 8 numbers which are both prime and in the fibonacci series using Python. I was just playing around since we were on the topic .

Code:
#!/usr/bin/env python
#output the first 8 numbers which are both prime and in fibonacci sequence

count=1
#initialize fibonachi numbers
(a,b)=(0,1)
fibonacci_numbers=[0,1]
#initialize prime numbers
current_num = 3
prime_numbers = [2]
#initialize a list for both prime and fibonnaci series numbers
both_prime_and_fibonacci = [2]


print "Calculating primes and fibonacci series (may take a while)..."
while count < 8:
  is_prime = True
  #check if the number is prime
  for item in prime_numbers:
    if current_num%item == 0:
      is_prime = False
  if is_prime:
    #is prime so add to prime number list
    prime_numbers.append(current_num)
    #grow the list of fibonacci numbers so that it is not less than the largest prime number
    while fibonacci_numbers[len(fibonacci_numbers)-1] < current_num:
      (a,b) = (b,a+b)
      fibonacci_numbers.append(a)
    #check to see if prime number is in the fibonacci sequence
    if current_num in fibonacci_numbers:
      both_prime_and_fibonacci.append(current_num)
      count = count+1
  #increment to the next odd number to be tested if prime
  current_num = current_num+2

#display the results
for item in both_prime_and_fibonacci:
  print item

#fibonacci sequence test
#(a,b)=(0,1)
#print "a= %d" % a
#for i in range(0,10):
#  (a,b)=(b,a+b)
#  print "a= %d" % a

Last edited by sag47; 09-02-2012 at 05:14 PM.
 
Old 09-02-2012, 11:39 PM   #9
kedarp
Member
 
Registered: Jul 2012
Location: Pune, India
Distribution: Mageia 4
Posts: 183

Rep: Reputation: 22
You can check the counter only till the sqrt of n for a prime no. That makes it more faster.

Code:
for(c=2;c<sqrt(n);c++){
...
}
 
Old 09-03-2012, 01:39 AM   #10
Skaperen
Senior Member
 
Registered: May 2009
Location: WV, USA
Distribution: Slackware, CentOS, Ubuntu, Fedora, Timesys, Linux From Scratch
Posts: 1,777
Blog Entries: 20

Rep: Reputation: 116Reputation: 116
Quote:
Originally Posted by kedarp View Post
You can check the counter only till the sqrt of n for a prime no. That makes it more faster.

Code:
for(c=2;c<sqrt(n);c++){
...
}
Certainly no need to overwork the loop beyond the square root. But the overhead of the sqrt() function is in there. We don't need it, though. We can stop the loop at the square root of n using another int and without a multiply.

Code:
int cc;
for(c=2,cc=3;(cc+cc-c)<n;c++,cc+=c){
...
}
I have not benchmarked if these added int steps beat the sqrt() function being added in there. They definitely do on some architectures.
 
Old 09-03-2012, 02:08 AM   #11
sag47
Senior Member
 
Registered: Sep 2009
Location: Philly, PA
Distribution: Kubuntu x64, RHEL, Fedora Core, FreeBSD, Windows x64
Posts: 1,506
Blog Entries: 35

Rep: Reputation: 383Reputation: 383Reputation: 383Reputation: 383
If we're talking about speed we can cut his number of loops in half by only checking odd numbers (like I did in my python source). No even number is prime since it is always divisible by two.
 
Old 09-03-2012, 01:15 PM   #12
Snark1994
Senior Member
 
Registered: Sep 2010
Location: Wales, UK
Distribution: Arch
Posts: 1,632
Blog Entries: 3

Rep: Reputation: 345Reputation: 345Reputation: 345Reputation: 345
Balvinder87, can you mark this thread as 'SOLVED' please? Thanks.

And if we're going to do it in other languages, then why not haskell:

Code:
isPrime n = n > 1 && foldr (\p yes -> p*p > n || ((n `rem` p) /= 0 && yes)) True primes
primes = 2 : filter isPrime [3,5..]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
primeFib x = (x `elem` (takeWhile (<=x) fibs)) && (isPrime x)
(Credit to HaskellWiki for an 'isPrime' one-liner)
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
PC-BSD (fibonacci) Partitioning explorer *BSD 6 05-27-2009 06:20 PM
Fibonacci generation without using temorary variable muskvar Programming 2 09-26-2007 09:16 AM
Fibonacci with fork BrokenFighter Programming 10 03-10-2007 10:41 PM
Big O notation - fibonacci sequence debiant Programming 13 09-10-2006 12:10 AM
need perl help calculating fibonacci numbers WorldBuilder Programming 5 12-17-2003 02:41 AM


All times are GMT -5. The time now is 09:01 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration